## 2.1 IntroductionPropositional Logic is concerned with propositions and their interrelationships. The notion of a proposition here cannot be defined precisely. Roughly speaking, a In this chapter, we first look at the syntactic rules that define the language of Propositional Logic. We then introduce the notion of a truth assignment and use it to define the meaning of Propositional Logic sentences. After that, we present a mechanical method for evaluating sentences for a given truth assignment, and we present a mechanical method for finding truth assignments that satisfy sentences. We conclude with some examples of Propositional Logic in formalizing Natural Language and Digital Circuits. ## 2.2 SyntaxIn Propositional Logic, there are two types of sentences -- simple sentences and compound sentences. Simple sentences express simple facts about the world. Compound sentences express logical relationships between the simpler sentences of which they are composed.
A (¬ A ( A ( An ( A ( Note that the constituent sentences within any compound sentence can be either simple sentences or compound sentences or a mixture of the two. For example, the following is a legal compound sentence. (( One disadvantage of our notation, as written, is that the parentheses tend to build up and need to be matched correctly. It would be nice if we could dispense with parentheses, e.g. simplifying the preceding sentence to the one shown below.
Unfortunately, we cannot do without parentheses entirely, since then we would be unable to render certain sentences unambiguously. For example, the sentence shown above could have resulted from dropping parentheses from either of the following sentences. (( ( The solution to this problem is the use of ∧ ∨ ⇒ ⇔ In sentences without parentheses, it is often the case that an expression is flanked by operators, one on either side. In interpreting such sentences, the question is whether the expression associates with the operator on its left or the one on its right. We can use precedence to make this determination. In particular, we agree that an operand in such a situation always associates with the operator of higher precedence. When an operand is surrounded by operators of equal precedence, the operand associates to the right. The following examples show how these rules work in various cases. The expressions on the right are the fully parenthesized versions of the expressions on the left.
Note that just because precedence allows us to delete parentheses in some cases does not mean that we can dispense with parentheses entirely. Consider the example shown earlier. Precedence eliminates the ambiguity by dictating that the sentence without parentheses is an implication with a disjunction as antecedent. However, this makes for a problem for those cases when we want to express a disjunction with an implication as a disjunct. In such cases, we must retain at least one pair of parentheses. We end the section with two simple definitions that are useful in discussing Propositional Logic. A ## 2.3 SemanticsThe treatment of semantics in Logic is similar to its treatment in Algebra. Algebra is unconcerned with the real-world significance of variables. What is interesting are the relationships among the values of the variables expressed in the equations we write. Algebraic methods are designed to respect these relationships, independent of what the variables represent. In a similar way, Logic is unconcerned with the real world significance of proposition constants. What is interesting is the relationship among the truth values of simple sentences and the truth values of compound sentences within which the simple sentences are contained. As with Algebra, logical reasoning methods are independent of the significance of proposition constants; all that matter is the form of sentences. Although the values assigned to proposition constants are not crucial in the sense just described, in talking about Logic, it is sometimes useful to make truth assignments explicit and to consider various assignments or all assignments and so forth. Such an assignment is called a truth assignment. Formally, a The assignment shown below is an example for the case of a propositional vocabulary with just three proposition constants, viz. p = 1^{i}q = 0^{i}r = 1
^{i}The following assignment is another truth assignment for the same vocabulary. p = 0^{i}q = 0^{i}r = 1
^{i}Note that the formulas above are not themselves sentences in Propositional Logic. Propositional Logic does not allow superscripts and does not use the = symbol. Rather, these are informal, metalevel statements Looking at the preceding truth assignments, it is important to bear in mind that, as far as logic is concerned, any truth assignment is as good as any other. Logic itself does not fix the truth assignment of individual proposition constants. On the other hand, If the truth value of a sentence is
The truth value of a conjunction is
The truth value of a disjunction is
The truth value of an implication is
A biconditional is
Using these definitions, it is easy to determine the truth values of compound sentences with proposition constants as constituents. As we shall see in the next section, we can determine the truth values of compound sentences with other compound sentences as parts by first evaluating the constituent sentences and then applying these definitions to the results. We finish up this section with a few definitions for future use. We say that a truth assignment ## 2.4 EvaluationEvaluation is the process of determining the truth values of compound sentences given a truth assignment for the truth values of proposition constants. As it turns out, there is a simple technique for evaluating complex sentences. We substitute true and false values for the proposition constants in our sentence, forming an expression with 1s and 0s and logical operators. We use our operator semantics to evaluate subexpressions with these truth values as arguments. We then repeat, working from the inside out, until we have a truth value for the sentence as a whole. As an example, consider the truth assignment p = 1^{i}q = 0^{i}r = 1
^{i}Using our evaluation method, we can see that p ∨ q) ∧ (¬ q ∨ r)(1 ∨ 0) ∧ (¬ 0 ∨ 1) 1 ∧ (¬ 0 ∨ 1) 1 ∧ (1 ∨ 1) 1 ∧ 1 1 Now consider truth assignment p = 0^{j}q = 1^{j}r = 0
^{j}In this case, p ∨ q) ∧ (¬q ∨ r)(0 ∨ 1) ∧ (¬1 ∨ 0) 1 ∧ (¬1 ∨ 0) 1 ∧ (0 ∨ 0) 1 ∧ 00 Using this technique, we can evaluate the truth of arbitrary sentences in our language. The cost is proportional to the size of the sentence. Of course, in some cases, it is possible to economize and do even better. For example, when evaluating a conjunction, if we discover that the first conjunct is false, then there is no need to evaluate the second conjunct since the sentence as a whole must be false. ## 2.5 Satisfaction
A The following figure shows a truth table for a propositional language with just three proposition constants (
Note that, for a propositional language with In solving satisfaction problems, we start with a truth table for the proposition constants of our language. We then process our sentences in turn, for each sentence placing an x next to rows in the truth table corresponding to truth assignments that do not satisfy the sentence. The truth assignments remaining at the end of this process are all possible truth assignments of the input sentences. As an example, consider the sentence
The disadvantage of the truth table method is computational complexity. As mentioned above, the size of a truth table for a language grows exponentially with the number of proposition constants in the language. When the number of constants is small, the method works well. When the number is large, the method becomes impractical. Even for moderate sized problems, it can be tedious. Even for an application like Sorority World, where there are only 16 proposition constants, there are 65,536 truth assignments. Over the years, researchers have proposed ways to improve the performance of truth table checking. However, the best approach to dealing with large vocabularies is to use symbolic manipulation (i.e. logical reasoning and proofs) in place of truth table checking. We discuss these methods in Chapters 4 and 5. ## 2.6 Example - Natural LanguageAs an exercise in working with Propositional Logic, let's look at the encoding of various English sentences as formal sentences in Propositional Logic. As we shall see, the structure of English sentences, along with various key words, such as The following examples concern three properties of people, and we assign a different proposition constant to each of these properties. We use the constant As our first example, consider the English sentence c ∨ f ⇒ pNext, we have the sentence p ⇒ c ∨ f
p ⇔ c ∨ fFinally, we have a negative sentence. c ∧ f)Note that, just because we can translate sentences into the language of Propositional Logic does not mean that they are true. The good news is that we can use our evaluation procedure to determine which sentences are true and which are false? Suppose we were to imagine a person who is cool and funny and popular, i.e. the proposition constants Using the evaluation procedure described earlier, we can see that, for this person, the first sentence is true.
c ∨ f ⇒ p(1 ∨ 1) ⇒ 1 1 ⇒ 1 1 The second sentence is also true.
p ⇒ c ∨ f1 ⇒ (1 ∨ 1) 1 ⇒ 1 1 Since the third sentence is really just the conjunction of the first two sentences, it is also true, which we can confirm directly as shown below.
p ⇔ c ∨ f 1 ⇔ (1 ∨ 1) 1 ⇔ 1 1 Unfortunately, the fourth sentence is not true, since the person in this case is both cool and funny.
c ∧ f)¬(1 ∧ 1) ¬1 0 In this particular case, three of the sentences are true, while one is false. The upshot of this is that there is no such person (assuming that the theory expressed in our sentences is correct). The good news is that there are cases where all four sentences are true, e.g. a person who is cool and popular but not funny or the case of a person who is funny and popular but not cool. Question to consider: What about a person is neither cool nor funny nor popular? Is this possible according to our theory? Which of the sentences would be true and which would be false? ## 2.7 Example - Digital CircuitsNow let's consider the use of Propositional Logic in modeling a portion of the physical world, in this case, a digital circuit like the ones used in building computers. The diagram below is a pictorial representation of such a circuit. There are three input Click on
p, q, r to toggle their values.At a given point in time, a node in a circuit can be either Given the Boolean nature of signals on nodes and the deterministic character of gates, it is quite natural to model digital circuits in Propositional Logic. We can represent each node of a circuit as a proposition constant, with the idea that the node is The sentences shown below capture the five gates in the circuit shown above. Node p ∧ ¬q) ∨ (¬p ∧ q) ⇔ or ∧ o ⇔ ap ∧ q ⇔ b( o ∧ ¬r) ∨ (¬o ∧ r) ⇔ sa ∨ b ⇔ cOnce we have done this, we can use our formalization to analyze the circuit - to determine if it meets it specification, to test whether a particular instance is operating correctly, and to diagnose the problem in cases here it is not. ## RecapThe syntax of Propositional Logic begins with a set of ## ProblemsProblem 2.1: Say whether each of the following expressions is a syntactically legal sentence of Propositional Logic.
Problem 2.2: Consider a truth assignment in which
Problem 2.3: A small company makes widgets in a variety of constituent materials (aluminum, copper, iron), colors (red, green, blue, grey), and finishes (matte, textured, coated). Although there are more than one thousand possible combinations of widget features, the company markets only a subset of the possible combinations. The following sentences are constraints that characterize the possibilities. Suppose that a customer places an order for a copper widget that is both green and blue with a matte coating. Your job is to determine which constraints are satisfied and which are violated.
Problem 2.4: Consider the sentences shown below. There are three proposition constants here, meaning that there are eight possible truth assignments. How many of these assignments satisfy all of these sentences?
Problem 2.5: A small company makes widgets in a variety of constituent materials (aluminum, copper, iron), colors (red, green, blue, grey), and finishes (matte, textured, coated). Although there are more than one thousand possible combinations of widget features, the company markets only a subset of the possible combinations. The sentences below are some constraints that characterize the possibilities. Your job here is to select materials, colors, and finishes in such a way that
Problem 2.6: Consider a propositional language with three proposition constants -
Problem 2.7: Consider the digital circuit described in section 2.7. Suppose we set nodes |