Question

Show that \(\\{\neg\\}\) is not a functionally complete set of connectives. Idem for \(\\{\rightarrow, \vee\\}\) (hint: show that each formula \(\varphi\) with only \(\rightarrow\) and \(\vee\) there is a valuation \(v\) such that \(\llbracket \varphi \rrbracket=1\) ).

Short answer

\(\{\neg\}\) and \(\{\rightarrow, \lor\}\) are not functionally complete because they can't express all logical functions.

Step-by-step solution

Understanding Functional Completeness

A set of logical connectives is functionally complete if every possible logical function can be expressed using only those connectives. Typically, sets like \(\{eg, \land\}\) are functionally complete because any logical expression can be rewritten using only these operations.

Analyzing \(\{\neg\}\)

To be functionally complete, \(\{eg\}\) alone must be able to express all logical functions, including \(\land\) and \(\lor\). However, \(eg\) can only flip the truth value of statements and cannot combine two statements to form \(\land\) or \(\lor\). Therefore, \(\{eg\}\) is not functionally complete.

Analyzing \(\{\rightarrow, \lor\}\)

To prove that \(\{\rightarrow, \lor\}\) is not functionally complete, show that there are logical functions that cannot be expressed using only these connectives.

Using the Hint to Analyze \(\{\rightarrow, \lor\}\)

The hint suggests finding a valuation \(v\) such that any formula \(\varphi\) in \(\{\rightarrow, \lor\}\) evaluates to \(1\). Construct a valuation where all propositions are true. For any s set of variables, each operand in a formula will evaluate to true, and thus any formula using only \(\rightarrow\) and \(\lor\) will also evaluate to true under this valuation, confirming these can't express all possible logical forms.

Conclusion

Since both sets \(\{eg\}\) and \(\{\rightarrow, \lor\}\) cannot produce all types of logical functions, they are not functionally complete.

Key concepts

Logical Connectives

Logical connectives are essential building blocks in mathematical logic, computer science, and philosophical logic. They connect simple statements to form more complex expressions. Common logical connectives include:

• "And" (\(\land\))
• "Or" (\(\lor\))
• "Not" (\(eg\))
• "If-then" (\(\rightarrow\))
• "If and only if" (\(\leftrightarrow\))

These connectives help define the truth conditions of complex statements based on the truth conditions of their simpler components.
Different sets of logical connectives can be functionally complete or incomplete. A functionally complete set can express any logical statement. On the contrary, an incomplete set lacks the ability to represent some logical functions.

Valuation

In logic, valuation is crucial for determining the truth value of a compound statement. It assigns a truth value to each proposition in a statement. For example, consider a proposition \(p\), which can either be true (\(1\)) or false (\(0\)).
Valuations are typically represented as functions, \(v\), that map propositions to truth values. Understanding valuations helps to evaluate the overall truth of logical expressions based on the truth of individual propositions.
In the context of proving the completeness of logical connectives, constructing a specific valuation where certain propositions evaluate to true or false can illustrate whether or not a set of connectives can express all logical forms.

Logical Functions

Logical functions refer to the output of logical connectives when applied to particular arguments. These functions can be very simple, such as returning a false value for every input, or more complex, like the identity that mimics the input value.
Examples include:

• Negation, which flips truth values.
• Conjunction, which is true only if both inputs are true.
• Disjunction, which is true if at least one input is true.
• Implication, which is false only when the first input is true, and the second is false.

Understanding logical functions is key to analyzing the expressive power of a set of logical connectives, determining if they cover all necessary logical operations.

Truth Values

Truth values are the basic units of semantic evaluation in logic. They represent the truth or falsity of a proposition and are most commonly denoted as \(1\) for "true" and \(0\) for "false".
These values form the foundation upon which logical statements are evaluated, as each connective modifies or combines them according to specific rules. For example, \(eg p\) changes a truth value \(1\) to \(0\), and vice versa.
In the context of proving the functional completeness of connectives, analyzing truth values under different valuations helps to determine whether a set can express every possible truth function.
This analysis is crucial to identifying limitations in logical connectives like \(\{eg\}\) and \(\{\rightarrow, \lor\}\), where certain evaluations always lead to a simplified outcome.