CHAPTER 2Logic1. Logic Definitions1.1. Propositions.Definition 1.1.1. A proposition is a declarative sentence that is eithertrue (denoted either T or 1) orfalse (denoted either F or 0).Notation: Variables are used to represent propositions. The most common variablesused are p, q, and r.DiscussionLogic has been studied since the classical Greek period ( 600-300BC). The Greeks,most notably Thales, were the first to formally analyze the reasoning process. Aristo-tle (384-322BC), the “father of logic”, and many other Greeks searched for universaltruths that were irrefutable. A second great period for logic came with the use of sym-bols to simplify complicated logical arguments. Gottfried Leibniz (1646-1716) beganthis work at age 14, but failed to provide a workable foundation for symbolic logic.George Boole (1815-1864) is considered the “father of symbolic logic”. He developedlogic as an abstract mathematical system consisting of defined terms (propositions),operations (conjunction, disjunction, and negation), and rules for using the opera-tions. It is this system that we will study in the first section.Boole’s basic idea was that if simple propositions could be represented by pre-cise symbols, the relation between the propositions could be read as precisely as analgebraic equation. Boole developed an “algebra of logic” in which certain types ofreasoning were reduced to manipulations of symbols.1.2. Examples.Example 1.2.1. “Drilling for oil caused dinosaurs to become extinct.” is a propo-sition.211. LOGIC DEFINITIONS 22Example 1.2.2. “Look out!” is not a proposition.Example 1.2.3. “How far is it to the next town?” is not a proposition.Example 1.2.4. “x + 2 = 2x” is not a proposition.Example 1.2.5. “x + 2 = 2x when x = −2” is a proposition.Recall a proposition is a declarative sentence that is either true or false. Here aresome further examples of propositions:Example 1.2.6. All cows are brown.Example 1.2.7. The Earth is further from the sun than Venus.Example 1.2.8. There is life on Mars.Example 1.2.9. 2 × 2 = 5.Here are some sentences that are not propositions.Example 1.2.10. “Do you want to go to the movies?” Since a question is not adeclarative sentence, it fails to be a proposition.Example 1.2.11. “Clean up your room.” Likewise, an imperative is not a declar-ative sentence; hence, fails to be a proposition.Example 1.2.12. “2x = 2 + x.” This is a declarative sentence, but unless x isassigned a value or is otherwise prescribed, the sentence neither true nor false, hence,not a proposition.Example 1.2.13. “This sentence is false.” What happens if you assume this state-ment is true? false? This example is called a paradox and is not a proposition, becauseit is neither true nor false.Each proposition can be assigned one of two truth values. We use T or 1 for trueand use F or 0 for false.1.3. Logical Operators.Definition 1.3.1. Unary Operator negation: “not p”, ¬p.Definitions 1.3.1. Binary Operators(a) conjunction: “p and q”, p ∧ q.(b) disjunction: “p or q”, p ∨ q.(c) exclusive or: “exactly one of p or q”, “p xor q”, p ⊕ q.(d) implication: “if p then q”, p → q.(e) biconditional: “p if and only if q”, p ↔ q.1. LOGIC DEFINITIONS 23DiscussionA sentence like “I can jump and skip” can be thought of as a combination of thetwo sentences “I can jump” and “I can skip.” When we analyze arguments or logicalexpression it is very helpful to break a sentence down to some composition of simplerstatements.We can create compound propositions using propositional variables, such asp, q, r, s, ..., and connectives or logical operators. A logical operator is either a unaryoperator, meaning it is applied to only a single proposition; or a binary operator,meaning it is applied to two propositions. Truth tables are used to exhibit the rela-tionship between the truth values of a compound proposition and the truth values ofits component propositions.1.4. Negation. Negation Operator, “not”, has symbol ¬.Example 1.4.1. p: This book is interesting.¬p can be read as:(i.) This book is not interesting.(ii.) This book is uninteresting.(iii.) It is not the case that this book is interesting.Truth Table:p ¬ pT FF TDiscussionThe negation operator is a unary operator which, when applied to a propositionp, changes the truth value of p. That is, the negation of a proposition p, denotedby ¬p, is the proposition that is false when p is true and true when p is false. Forexample, if p is the statement “I understand this”, then its negation would be “I donot understand this” or “It is not the case that I understand this.” Another notationcommonly used for the negation of p is ∼ p.Generally, an appropriately inserted “not” or removed “not” is sufficient to negatea simple statement. Negating a compound statement may be a bit more complicatedas we will see later on.1. LOGIC DEFINITIONS 241.5. Conjunction. Conjunction Operator, “and”, has symbol ∧.Example 1.5.1. p: This book is interesting. q: I am staying at home.p ∧ q: This book is interesting, and I am staying at home.Truth Table:p q p ∧ qT T TT F FF T FF F FDiscussionThe conjunction operator is the binary operator which, when applied to two propo-sitions p and q, yields the proposition “p and q”, denoted p∧q. The conjunction p∧q ofp and q is the proposition that is true when both p and q are true and false otherwise.1.6. Disjunction. Disjunction Operator, inclusive “or”, has symbol ∨.Example 1.6.1. p: This book is interesting. q: I am staying at home.p ∨ q: This book is interesting, or I am staying at home.Truth Table:p q p ∨ qT T TT F TF T TF F FDiscussionThe disjunction operator is the binary operator which, when applied to two propo-sitions p and q, yields the proposition “p or q”, denoted p ∨ q. The disjunction p ∨ qof p and q is the proposition that is true when either p is true, q is true, or both aretrue, and is false otherwise. Thus, the “or” intended here is the inclusive or. In fact,the symbol ∨ is the abbreviation of the Latin word vel for the inclusive “or”.1. LOGIC DEFINITIONS 251.7. Exclusive Or. Exclusive Or Operator, “xor”, has symbol ⊕.Example 1.7.1. p: This book is interesting. q: I am staying at home.p ⊕ q: Either this book is interesting, or I am staying at home, but not both.Truth Table:p q p ⊕ qT T FT F TF T TF F FDiscussionThe exclusive or is the binary operator which,