Chapter Summary
Propositional Logic
- The Language of Propositions
- Applications
- Logical Equivalences
Predicate Logic
- The Language of Quantifiers
Propositional Logic
Propositions
A proposition is a declarative sentence that is either true or false.
Propositional Logic
Constructing Propositions
- Propositional Variables: p, q, r, s, …
- The proposition that is always true is denoted by T and the proposition that is always false is denoted by F.
Compound Propositions; constructed from logical connectives and other propositions.
- Negation ¬
- Conjunction ∧
- Disjunction ∨
- Implication →
- Biconditional ↔
Compound Proposition
Negation
The negation of a proposition p is denoted by ¬p and has this truth table :
| p | ¬p |
|---|---|
| T | F |
| F | T |
Conjunction
The conjunction of propositions p and q is denoted by p ∧ q and has this truth table :
| p | q | p ∧ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | T | F |
Disjunction
The disjunction of propositions p and q is denoted by p ∨ q and has this truth table :
| p | q | p ∨ q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
The Connective Or in English
In English “or” has two distinct meanings.
Inclusive Or
- For p ∨ q to be true, either one or both of p and q must be true.
Exclusive Or (Xor)
- In p ⊕ q , one of p and q must be true, but not both.
- The truth table for ⊕ is :
| p | q | p ⊕ q |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
Implication
If p and q are propositions, then p → q is a conditional statement or implication which is read as “if p, then q” and has this truth table :
| p | q | p → q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
In p → q , p is the hypothesis (antecedent or premise) and q is the conclusion (or consequence).
Understanding Implication
In p → q there does not need to be any connection between the antecedent or the consequent. The “meaning” of p →q depends only on the truth values of p and q.
These implications are perfectly fine, but would not be used in ordinary English.
- “If the moon is made of green cheese, then I have more money than Bill Gates. ”
- “If the moon is made of green cheese then I’m on welfare.”
- “If 1 + 1 = 3, then your grandma wears combat boots.”
One way to view the logical conditional is to think of an obligation or contract.
- “If I am elected, then I will lower taxes.”
- “If you get 100% on the final, then you will get an A.”
If the politician is elected and does not lower taxes, then the voters can say that he or she has broken the campaign pledge. Something similar holds for the professor. This corresponds to the case where p is true and q is false.
Different Ways of Expressing p → q
- if p, then q
- if p, q
- q unless ¬p
- q if p
- whenever p
- q follows from p
- p implies q
- p only if q
- q when p
- p is sufficient for q
- q is necessary for p
- a necessary condition for p is q
- a sufficient condition for q is p
Converse, Contrapositive, and Inverse
From p → q we can form new conditional statements.
- q → p is the converse of p → q (SWAP)
- ¬q → ¬p is the contrapositive of p → q (SWAP + NEGATE)
- ¬p → ¬q is the inverse of p → q (NEGATE)
Example: Find the converse, inverse, and contrapositive of “It’s raining is a sufficient condition for my not going to town.” This is equivalent to “If It’s raining, then I am not going to town.”
Solution:
converse: If I do not go to town, then it is raining.
inverse: If it is not raining, then I will go to town.
contrapositive: If I go to town, then it is not raining.
Biconditional
If p and q are propositions, then we can form the biconditional proposition p ↔ q , read as “p if and only if q.” The biconditional p ↔ q denotes the proposition with this truth table :
| p | q | p ↔ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
The biconditional statement p ↔ q is true when p and q have the same truth values, and is false otherwise. Biconditional statements are also called bi-implications.
If p denotes “I am at home.” and q denotes “It is raining.”, then p ↔ q denotes “I am at home if and only if it is raining.”
Expressing the Biconditional
Some alternative ways “p if and only if q” is expressed in English :
- p is necessary and sufficient for q
- if p then q , and conversely
- p iff q
Precedence of Logical Operators
| Operator | Precedence |
|---|---|
| ¬ | 1 |
| ∧ | 2 |
| ∨ | 3 |
| → | 4 |
| ↔ | 5 |
Truth Tables For Compound Propositions
How many rows are there in a truth table with n propositional variables?
Solution: Each propositional variable’s value can be T or F, therefore, there are $ 2^{n} $ rows in a truth table with n variables.
Note that this means that with n propositional variables, we can construct $ 2^{n} $ distinct (not equivalent) propositions.
How to fill up the rows – the combinations of values for the atomic propositions.
Solution:
- Start in the left-most column, divide it evenly, fill the first half with T’s and the second half with F’s.
- Then move right to the next column, repeat the previous step in the first half of the column and the second half of the column. Repeat until the last column is filled with alternating T's and F's.
- The first row will be all T's.
- The last row will be all F's.
Equivalent Propositions
Two propositions are equivalent if they always have the same truth value.
Example: Show using a truth table that the conditional is equivalent to the contrapositive.
Solution:
| p | q | ¬p | ¬q | p → q | ¬q → ¬p |
|---|---|---|---|---|---|
| T | T | F | F | T | T |
| T | F | F | T | F | F |
| F | T | T | F | T | T |
| F | F | T | T | T | T |
Logic and Bit Operations
Computers represent information using bits.
A bit is a symbol with two possible values, namely, 0 (zero) and 1 (one).
A bit can be used to represent a truth value, because there are two truth values, namely, true and false.
| Truth Values | Bit |
|---|---|
| T | 1 |
| F | 0 |
Customarily, we will use a 1 bit to represent true and a 0 bit to represent false. That is, 1 represents T (true), 0 represents F (false).
A variable is called a Boolean variable if its value is either true or false. Consequently, a Boolean variable can be represented using a bit.
Computer bit operations correspond to the logical connectives.
- Bitwise OR (∨, Disjunction, Inclusive OR)
- Bitwise AND (∧, Conjunction)
- Bitwise XOR (⊕, Disjunction, Exclusive OR)
A bit string is a sequence of zero or more bits. The length of this string is the number of bits in the string.
Example: Find the bitwise OR, bitwise AND, and bitwise XOR of the bit strings 01 1011 0110 and 11 0001 1101.
Applications of Propositional Logic
Boolean Searches
Logical connectives are used extensively in searches of large collections of information, such as indexes of Web pages. In Boolean searches,
| Connective | |
|---|---|
| And | match records that contain both of two search terms |
| Or | match one or both of two search terms |
| Not | exclude a particular search term. (sometimes written as AND NOT ) |
Web Page Searching Most Web search engines support Boolean searching techniques, which usually can help find Web pages about particular subjects.
Logic Circuits
Electronic circuits: each input/output signal can be viewed as a 0 or 1.
- 0 represents False
- 1 represents True
Complicated circuits are constructed from three basic circuits called gates.
We will study logic circuits in great details in Boolean Algebra.
Propositional Equivalences
Tautologies, Contradictions, and Contingencies
A tautology is a proposition which is always true.
- Example: p ∨ ¬p
A contradiction is a proposition which is always false.
- Example: p ∧ ¬p
- A contingency is a proposition which is neither a tautology nor a contradiction, such as p
| P | ¬p | p ∨ ¬p | p ∧ ¬p |
|---|---|---|---|
| T | F | T | F |
| F | T | T | F |
Logically Equivalent
Two compound propositions p and q are logically equivalent if p ↔ q is a tautology.
We write this as p ⇔ q or as p ≡ q where p and q are compound propositions.
Two compound propositions p and q are equivalent if and only if the columns in a truth table giving their truth values agree.
This truth table shows that ¬p ∨ q is equivalent to p → q.
| p | q | ¬p | ¬p ∨ q | p → q |
|---|---|---|---|---|
| T | T | F | T | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
De Morgan’s Laws
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q
Key Logical Equivalences
Identity Laws
- p ∧ T ≡ p
- p ∨ F ≡ p
Domination Laws
- p ∨ T ≡ T
- p ∧ F ≡ F
Idempotent laws
- p ∨ p ≡ p
- p ∧ p ≡ p
Double Negation Law
- ¬(¬p) ≡ p
Negation Laws
- p ∨ ¬p ≡ T
- p ∧ ¬p ≡ F
Commutative Laws
- p ∨ q ≡ q ∨ p
- p ∧ q ≡ q ∧ q
Associative Laws
- (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
- (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
Distributive Laws
- p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
- p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
Absorption Laws
- p ∨ (p ∧ q) ≡ p
- p ∧ (p ∨ q) ≡ p
More Logical Equivalences
Logical Equivalences Involving Conditional Statements
- p → q ≡ ¬p ∨ q
- p → q ≡ ¬q → ¬p
- p ∨ q ≡ ¬p → q
- p ∧ q ≡ ¬(p → ¬q)
- ¬(p → q) ≡ p ∧ ¬q
- (p → q) ∧ (p → r) ≡ p → (q ∧ r)
- (p → r) ∧ (q → r) ≡ (p ∨ q) → r
- (p → q) ∨ (p → r) ≡ p → (q ∨ r)
- (p → r) ∨ (q → r) ≡ (p ∧ q) → r
Logical Equivalencecs Involving Biconditional Statements
- p ↔ q ≡ (p → q) ∧ (q → p)
- p ↔ q ≡ ¬p ↔ ¬q
- p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)
- ¬(p ↔ q) ≡ p ↔ ¬q
Predicates and Quantifiers
Propositional logic cannot adequately express the meaning of all statements in mathematics and in natural language.
Need a language, predicate logic, that talks about objects, their properties, and their relations.
Predicate logic can be used to express the meaning of a wide range of statements in mathematics and computer science in ways that permit us to reason and explore relationships between objects.
Introducing Predicate Logic
Predicate logic uses the following new features :
- Variables: x, y, z
- Predicates: P(x), M(x)
- Quantifiers
Propositional functions are a generalization of propositions.
- They contain variables and a predicate, e.g., P(x)
- Variables can be replaced by elements from their domain.
We can denote the statement “x is greater than 3” by P(x), where P denotes the predicate “is greater than 3” and x is the variable.
The statement P(x) is also said to be the value of the propositional function P at x.
Once a value has been assigned to the variable x, the statement P(x) becomes a proposition and has a truth value.
Propositional Functions
For example, let P(x) denote “x > 0” and the domain be the integers.
- P(-3) is false.
- P(0) is false.
- P(3) is true.
Often the domain is denoted by U. So in this example U is the integers.
In general, a statement involving the n variables $ x_{1} , x_{2}, ... , x_{n} $ can be denoted by
$$ P(x_{1} , x_{2}, ... , x_{n}) $$
A statement of the form $ P(x_{1} , x_{2}, ... , x_{n}) $ is the value of the propositional function P at the n-tuple ($ x_{1} , x_{2}, ... , x_{n} $), and P is also called an n-place predicate or a n-ary predicate.
Quantifiers
Quantification expresses the extent to which a predicate is true over a range of elements.
We need quantifiers to express the meaning of English words including all and some :
- “All men are Mortal."
- “Some cats do not have fur.”
The area of logic that deals with predicates and quantifiers is called the predicate calculus.
Many mathematical statements assert that a property is true for all values of a variable in a particular domain, called the domain of discourse (or the universe of discourse), often just referred to as the domain.
The two most important quantifiers are :
- Universal Quantifier, “For all,” symbol: ∀
- Existential Quantifier, “There exists,” symbol: ∃
∀x P(x) asserts P(x) is true for every x in the domain.
∃x P(x) asserts P(x) is true for some x in the domain.
Universal Quantifier
∀x P(x) is read as “For all x, P(x)” or “For every x, P(x).”
Existential Quantifier
∃x P(x) is read as “For some x, P(x)”, or as “There is an x such that P(x),” or “For at least one x, P(x).”
Precedence of Quantifiers
The quantifiers ∀ and ∃ have higher precedence than all the logical operators.
De Morgan’s Laws for Quantifiers
The rules for negating quantifiers are :
Logic Programming
Prolog (from Programming in Logic) is a programming language developed in the 1970s by researchers in artificial intelligence (AI).
Prolog programs include Prolog facts and Prolog rules.
There is much more at Learn Prolog Now! to Prolog and to the entire field of logic programming.
Thanks for the learning resource provided by Qi Wang from University at Albany!