Question

(Depends on the Exercise Set in Section 1.3)

a) Given a truth table, explain how to use disjunctive normal form to construct a compound proposition with this truth table.

b) Explain why part (a) shows that the operators∧,∨, and ¬ are functionally complete.

c) Is there an operator such that the set containing just this operator is functionally complete?

Short answer

(a) It is sufficient to know how to construct truth tables for conjunctions \( \wedge \), disjunctions \( \vee \)and negations \(\neg \), while constructing truth table.

(b) All compound propositions can be written using only the operators, \( \wedge ,\; \vee \), and \(\neg \).

(c) No

Step-by-step solution

Meaning of symbol \(\neg \).

The meaning of proposition \(\neg p\) is “not p.” The truth value of the negation of\(\neg p\), is the opposite of the truth value of p.

Explain method to use disjunctive normal form to construct a compound proposition with this truth table

(a)

A proposition is in disjunctive normal form, if it only contains the operators \( \wedge ,\; \vee \), and \(\neg \).

Conditional and biconditional statements can be rewritten in disjunctive normal form using the following logical equivalences.

\(\begin{aligned}{}p \to q \equiv \neg p \vee q\\p \leftrightarrow q \equiv \left( {p \wedge q} \right) \vee \left( {\neg p \wedge \neg q} \right)\end{aligned}\)

When constructing truth tables, it is sufficient to know how to construct truth tables for conjunctions \( \wedge \), disjunctions \( \vee \)and negations \(\neg \).

A conjunction \(p \wedge q\) is true, if both propositions are true.

A disjunction \(p \vee q\) is true, if either of the propositions are true.

A negation \(\neg p\) is true, if the proposition \(p\) is false.

Explain the reason why the operators∧, ∨, and ¬ are functionally complete

(b)

A set of operators are functionally complete, if all compound propositions can be written using only the operators in the set of operators.

The operators \( \wedge ,\; \vee \), and \(\neg \)are functionally complete, because conditional an bi-conditional statements can be rewritten with only the operators \( \wedge ,\; \vee \), and \(\neg \), thus all compound propositions can be written using only the operators \( \wedge ,\; \vee \), and \(\neg \).

Determine whether there is a functionally complete set

(c)

There is no functionally complete set of operators containing only one operator, because it is required at the very least the negation \(\neg \) and either the disjunction \( \vee \) or conjunction \( \wedge \).

For example, no one can write \(\neg p\) by using only conjunction or disjunction, and cannot rewrite \(p \vee q\) using only negation.