In a three-valued logic systems, how many rows are
needed for a truth table with n statement letters?
Answers
Answer:
Classically, we think of propositional variables as ranging over statements that can be true or false. And, intuitively, we think of a proof system as telling us what propositional formulas have to be true, no matter what the variables stand for. For example, the fact that we can prove C from the hypotheses A, B, and A∧B→C seems to tell us that whenever the hypotheses are true, then C has to be true as well.
Making sense of this involves stepping outside the system and giving an account of truth—more precisely, the conditions under which a propositional formula is true. This is one of the things that symbolic logic was designed to do, and the task belongs to the realm of semantics. Formulas and formal proofs are syntactic notions, which is to say, they are represented by symbols and symbolic structures. Truth is a semantic notion, in that it ascribes a type of meaning to certain formulas.
Syntactically, we were able to ask and answer questions like the following:
Given a set of hypotheses, Γ, and a formula, A, can we derive A from Γ?
What formulas can be derived from Γ?
What hypotheses are needed to derive A?
The questions we consider semantically are different:
Given an assignment of truth values to the propositional variables occurring in a formula A, is A true or false?
Is there any truth assignment that makes A true?
Which are the truth assignments that make A true?
In this chapter, we will not provide a fully rigorous mathematical treatment of syntax and semantics. That subject matter is appropriate to a more advanced and focused course on mathematical logic. But we will discuss semantic issues in enough detail to give you a good sense of what it means to think semantically, as well as a sense of how to make pragmatic use of semantic notions.