Propositions and Logical Operations

Proposition

A proposition or statement is a sentence which is either true or false.
Definition:If a proposition is true, then we say its truth value is true, and if a proposition is false, we say its truth value is false.

Example:
Are the following sentences propositions?
 The table is made of wood.
Enter the class!
5+2=7
x+y > 12
 Is it hurt?
Sentences 1 and 2 are not propositions because they are not declarative sentences. Sentences 3 and 4 are not propositions because they are neither true nor false.

LOGICAL CONNECTIVES

• Use logical connectives to build complex propositions from simpler ones.

The First Three Logical Connectives
• ¬ denotes not. ¬P is the negation of P.
• ∨ denotes or. P ∨ Q is the disjunction of P and Q.
• ∧ denotes and. P ∧ Q is the conjunction of P and Q.
Order of Operations
• ¬ first
• ∧/∨ second
• implication and biconditionals last (more on these later)
• parentheses can be used to change the order

NEGATION (¬)

DEFINITION 1
Let p be a proposition. The negation of p, denoted by ¬p, is the statement
“It is not the case that p.”
The proposition ¬p is read “not p.” The truth value of the negation of p, ¬p is the opposite of the truth value of p.

The Truth Table for the Negation of a Proposition.
P     ¬p
T      F
F      T
  • Logical operators (connectives) are used to form new propositions from two or more existing propositions.
EXAMPLE
Find the negation of the proposition “Today is sunny day.” and express this in simple English.
The negation is “It is not the case that today is sunny day.” In simple English, “Today is not sunny day.” or “It is not sunny day today.”

CONJUNCTION

DEFINITION 3
Let p and q be propositions. The conjunction of p and q, denoted by p ˄ q, is the proposition “p and q”. The conjunction p ˄ q is true when both p and q are true and is false otherwise.
The Truth Table for the Conjunction of two Proposition
P     Q     p˄q
T     T      T
T     F      F
F     T      F
F     F      F
Example
Find the conjunction of the propositions p and q where p is the proposition “Tony’s handphone has less than 15 GB phone storage” and q is the proposition “The processor in Tony’s handphone runs slower than 1 GHz.”
Solution: The conjunction of these propositions, p ∧ q, is the proposition “Tony’s handphone has less than 15 GB phone storage, and the processor in Tony’s handphone runs slower than 1 GHz.” This conjunction can be expressed more simply as “Tony’s handphone has less than 15 GB phone storage it’s processor runs slower than 1 GHz.” For this conjunction to be true, both conditions given must be true. It is false, when one or both of these conditions are false. Note that in logic the word “but” sometimes is used instead of “and” in a conjunction.

DISJUNCTION

DEFINITION 4
Let p and q be propositions. The disjunction of p and q, denoted by p ˅ q, is the proposition
“p or q.” The disjunction p ˅ q is false when both p and q are false and is true otherwise.
The Truth Table for the Disjunction of two Proposition
p     Q     p ˅ q
T     T     T
T     F     T
F     T     T
F     F     F
  • Examples
Find the conjunction of the propositions p and q where p is the proposition “Tony’s handphone has at most 15 GB phone storage” and q is the proposition “The processor in Tony’s handphone runs slower than 1 GHz.”
Solution: The conjunction of these propositions, p ∧ q, is the proposition “Tony’s handphone has less than 15 GB phone storage, or the processor in Tony’s handphone runs slower than 1 GHz.”
This proposition is true when Tony’s handphone has less than 15 GB phone storage, when the processor in Tony’s handphone runs slower than 1 GHz, and when both conditions are true. It is false when both of these conditions are false, that is, when Tony’s handphone has less than 15 GB phone storage and the processor in handphone runs at 1 GHz or slower.

EXCLUSIVE OR (P ⊕ Q)

DEFINITION 5

Let p and q be propositions. The exclusive or of p and q, denoted by p ⊕ q, is the proposition that is true when exactly one of p and q is true and is false otherwise.
The Truth Table for the exclusive or of two Proposition
P     Q     p ⊕ q
T     T      F
T     F     T
F     T     T
F     F     F
Example
Find the exclusive or of the propositions p and q where p is the proposition “Tony’s handphone has at most 15 GB phone storage” and q is the proposition “The processor in Tony’s handphone runs slower than 1 GHz.”
Solution: The conjunction of these propositions, p ∧ q, is the proposition “Tony’s handphone has at most 15 GB phone storage, or the processor in Tony’s handphone runs slower than 1 GHz.”
This proposition is true when Tony’s handphone has at most 15 GB phone storage, when the processor in Tony’s handphone runs slower than 1 GHz, and when both conditions are true. It is false when both of these conditions are false, that is, when Tony’s handphone has more than 15 GB phone storage and the processor in handphone runs at 1 GHz or faster.

CONDITIONAL STATEMENTS(IMPLICATION) (P→Q)

A proposition or statement is a sentence which is either true or false.
Definition:If a proposition is true, then we say its truth value is true, and if a proposition is false, we say its truth value is false.

DEFINITION 6
 Let p and q be propositions. The conditional statement p → q is the proposition “if p, then
q.” The conditional statement p → q is false when p is true and q is false, and true otherwise.
In the conditional statement p → q, p is called the hypothesis (or antecedent or premise)
and q is called the conclusion (or consequence).
The Truth Table for the Conditional Statements of two Proposition
p     q     p → q
T     T     T
T     F     F
F     T     T
F     F     T
terminology is used to express p → q.
“if p, then q”      “p implies q”
“if p, q”              “p only if q”
“p is sufficient for q”  
“a sufficient condition for q is p”
“q if p”               “q whenever p”
“q when p”        “q is necessary for p”
“a necessary condition for p is q”
“q follows from p” 
“q unless ¬p”
EXAMPLE
Let p be the statement “Lim eat rotten apple” and q the statement “Lim will get stomach pain.” Express the statement p → q as a statement in English.
Solution: From the definition of conditional statements, we see that when p is the statement
“Lim eat rotten apple” and q is the statement “Lim will get stomach pain,” p → q
represents the statement
“If Lim eat rotten apple, then she will get stomach pain.”
There are many other ways to express this conditional statement in English. Among the most
natural of these are:
“Lim will get stomach pain when she eat rotten apple.”
“Lim will get stomach pain unless she does not eat rotten apple.”
EXAMPLE
What is the value of the variable x after the statement if 2 + 2 = 4 then x := x + 1
if x = 0 before this statement is encountered? (The symbol := stands for assignment. The
statement x := x + 1 means the assignment of the value of x + 1 to x.)

Solution: Because 2 + 2 = 4 is true, the assignment statement x := x + 1 is executed. Hence,
x has the value 0 + 1 = 1 after this statement is encountered.

CONVERSE, CONTRAPOSITIVE, AND INVERSE

• Use logical connectives to build complex propositions from simpler ones.

Conditional Statements
p → q
If p, then q
Converse
q → p
If q, then p
Contrapositive
¬ q → ¬ p
If not p, then not q
Inverse
¬ p →¬ q
If not q, then not p
Example
What are the converse, and the inverse and the contrapositive of the conditional statement
“If it is raining, then the air smells fresh.”
 Let p= If it is raining, q= the air smells fresh
Converse: If the air smells fresh, then it is raining.
Inverse: If it is not raining, then the air is not smells fresh.
Contrapositive: If the air is not smells fresh, then it is not raining.

BICONDITIONAL statement(bi-implications)

Let p and q be propositions. The biconditional statement p ↔ q is the proposition “p if
and only if q.” The biconditional statement p ↔ q is true when p and q have the same truth
values, and is false otherwise.

The Truth Table for the Biconditional Statements of two Proposition
p     q     p ↔ q
T     T     T
T     F     F
F     T     F
F     F     T
Example
Let p be the statement “An angle is acute angle” and let q be the statement “It has a measure of less than 90˚”.
Solution
An angle is acute angle if and only if it has a measure of less than 90˚.

This statement is true if p and q are either both true or both false, that is, if you buy a ticket and
can take the flight or if you do not buy a ticket and you cannot take the flight. It is false when
p and q have opposite truth values, that is, when you do not buy a ticket, but you can take the
flight (such as when you get a free trip) and when you buy a ticket but you cannot take the flight
(such as when the airline bumps you).

There are some other common ways to express p ↔ q:   
“p is necessary and sufficient for q”
“if p then q, and conversely”
“p iff q.”
The last way of expressing the biconditional statement p ↔ q uses the abbreviation “iff” for
“if and only if.”

Precedence of Logical Operators

DEFINITION 6
 Let p and q be propositions. The conditional statement p → q is the proposition “if p, then
q.” The conditional statement p → q is false when p is true and q is false, and true otherwise.
In the conditional statement p → q, p is called the hypothesis (or antecedent or premise)
and q is called the conclusion (or consequence).
The Truth Table for the Conditional Statements of two Proposition
p     q     p → q
T     T     T
T     F     F
F     T     T
F     F     T
terminology is used to express p → q.
“if p, then q”      “p implies q”
“if p, q”              “p only if q”
“p is sufficient for q”  
“a sufficient condition for q is p”
“q if p”               “q whenever p”
“q when p”        “q is necessary for p”
“a necessary condition for p is q”
“q follows from p” 
“q unless ¬p”
EXAMPLE
Let p be the statement “Lim eat rotten apple” and q the statement “Lim will get stomach pain.” Express the statement p → q as a statement in English.
Solution: From the definition of conditional statements, we see that when p is the statement
“Lim eat rotten apple” and q is the statement “Lim will get stomach pain,” p → q
represents the statement
“If Lim eat rotten apple, then she will get stomach pain.”
There are many other ways to express this conditional statement in English. Among the most
natural of these are:
“Lim will get stomach pain when she eat rotten apple.”
“Lim will get stomach pain unless she does not eat rotten apple.”
EXAMPLE
What is the value of the variable x after the statement if 2 + 2 = 4 then x := x + 1
if x = 0 before this statement is encountered? (The symbol := stands for assignment. The
statement x := x + 1 means the assignment of the value of x + 1 to x.)

Solution: Because 2 + 2 = 4 is true, the assignment statement x := x + 1 is executed. Hence,
x has the value 0 + 1 = 1 after this statement is encountered.
X  y  x∧y  x∨y  x⊕y
0  0   0      0      0
0  1   0      1      1
1  0   0      1      1
1  1   1      1      0
Find the bitwise ∧, ∨ and ⊕of the bit strings 10 0001 1110 and 01 1101 1101.
Solution
10 0001 1110
01 1101 1101
00 0000 1100    bitwise ∧
11 1101 1111   bitwise ∨
11 1100 0011   bitwise ⊕

Truth table of compound composition

Example

Construct the truth table of (p → q) ∨( ¬ p→ q).

P q p→q ¬p  ¬p→q (p→q)∨(¬p→q)
T T    T      F       T              T
T F    F      F       T              T
F T    T      T       T              T
F F    T      T       F              T
Example
Construct the truth table of ¬( p ∧ q) and ¬ p ∨ ¬q. What can be concluded?
P q p∧q ¬(p∧q) ¬p ¬q ¬p∨¬q
T T   T        F      F   F       F
T F   F        T      F   T       T
F T   F        T      T   F       T
F F   F        T      T   T       T
It can be concluded that ¬( p ∧ q) ≡ ¬ p ∨ ¬q.(De Morgan’s Law)

PREDICATES AND QUANTIFIERS

Predicates
Statements involving variables, such as x < 5 and computer x is low on memory.
The statement “x is smaller than 5” has two parts. The first part, the variable x, is the subject of the statement. The second part—the predicate, “is smaller than 3”—refers to a property that the subject of the statement can have. We can denote the statement “x is greater than 3” by P(x), where P denotes the predicate “is smaller than 5” and x is the variable. The statement P(x) is also said to be the value of the propositional function Pat x. When a value has been assigned to the variable x, the statement P(x) becomes a proposition and has a truth value.
Example
Let P(x) denote the statement “x > 8.” What are the truth values of P(6) and P(9)?
Solution: We obtain the statement P(6) by setting x = 6 in the statement “x > 8.” Hence,
P(6), which is the statement “6 > 8,” is false. P(9), which is the statement “9 > 8,”
is true. We can also have statements that involve more than one variable. For instance, consider the
statement “x = y + 3.” We can denote this statement by Q(x, y), where x and y are variables
and Q is the predicate. When values are assigned to the variables x and y, the statement Q(x, y) has a truth value.


Example
Let A(x) denote the statement “Table x is full of drinks.” Suppose that of the table in the class, only wooden table and stainless steel table are currently full of drinks. What are truth values of A(wooden table), A(stainless steel table), and A(glass table)?
Solution: We obtain the statement A(glass table) by setting x = glass table in the statement “Table x is full of drinks.” Because glass table is not on the list of table currently full of drinks, we conclude that A(glass table) is false. Similarly, because wooden table and stainless steel table are on the list of table currently full of drinks, we know that A(wooden table) and A(stainless steel table) are true.


Let R (x, y, z) denote the statement x - y = z. What are the truth values of the propositions R(6, 2, 4) and R(7, 5, 4)?
Solution: The proposition R (6, 2, 4) is obtained by setting x = 6, y = 2, and z = 4 in the
statement R(x, y, z). We see that R(6, 2, 4) is the statement “6 - 2 = 4,” which is true. Also
note that R(7, 5, 4), which is the statement “ 7 - 5 = 4,” is false.

QUANTIFIERS

Quantifiers
- words that refer to quantities such as ”some” or ”all” and tell for how many elements a given predicate is true. In English, the words all, some,
- many, none, and few are used in quantifications.
Universal Quantifier
The symbol ∀ denotes ”for all”
The universal quantification of P(x) is the statement
“P(x) for all values of x in the domain.”
The notation ∀xP(x) denotes the universal quantification of P(x). Here ∀ is called the universal quantifier. We read ∀xP(x) as “for all xP(x)” or “for every xP(x).” An element for which P(x) is false is called a counterexample of ∀xP(x).
Other ways to express universal quantifier
- “all of,” “for each,” “given any,” “for arbitrary,” “for each,” and “for any.”
Existential Quantifier
The symbol ∃ denotes ”there exists”
The existential quantification of P(x) is the proposition
“There exists an element x in the domain such that P(x).”
We use the notation ∃xP(x) for the existential quantification of P(x). Here ∃ is called the existential quantifier.
Other ways to express existential quantification
- “for some,” “for at least one,” or “there is.”
∀xP(x)
 is true for every x.
There is an x for which P(x) is false.
xP(x)
There is an x for which P(x) is true.
P(x) is false for every x.
Example
Let P(x) be the statement ”. What is the truth value of the quantification ∀xP(x),
where the domain consists of all real numbers?
Solution: Because P(x) is true for all real numbers x, the quantification ∀xP(x) is T.

Example

Let P(x) denote the statement “x > 7.” What is the tru          th value of the quantification ∃xP(x),
where the domain consists of all real numbers?
Solution: Because “x > 3” is sometimes true—for instance, when x = 9—the existential quantification of P(x), which is ∃xP(x), is T.


However,
there is no limitation on the number of different quantifiers we can define, such as “there are
exactly two,” “there are no more than three,” “there are at least 100,” and so on. Of these other
quantifiers, the one that is most often seen is the uniqueness quantifier, denoted by ∃! or ∃1.

NEGATING QUANTIFIED EXPRESSIONS

De Morgan’s Law
¬∃xP(x)
∀x¬P(x)
For every x, P(x) is false.
There is an x for which P(x) is true.
¬∀xP(x)
∃x¬P(x)
There is an x for which P(x) is false
P(x) is true for every x.
Example
What are the negations of the statements “There is a fair employer” and “All rabbit eat carrot”?
Let H(x) denote “x is cute.” Then the statement “There is an fair employer” is represented by ∃xH(x), where the domain consists of all employer. The negation of this statement is ¬∃xH(x), which is equivalent to ∀x¬H(x). This negation can be expressed as “Every employer is not fair.”
Let C(x) denote “x eats carrot.” Then the statement “All rabbit eat carrot” is represented by ∀xC(x), where the domain consists of all rabbit. The negation of this statement is ¬∀xC(x), which is equivalent to ∃x¬C(x). This negation can be expressed in several different ways, including “Some rabbit does not eat carrot” and “There is an rabbit who does not eat carrot.”

Example
What are the negations of the statements ∀x(x^2<2x)  and ∃x(x≠8)?
 ¬∀x(x^2<2x)=∃x ¬(x^2<2x)
                       = ∃x¬(x^2<2x)
∃x(x≠8)=∀x ¬(x≠8)
            =∀x ¬(x=8)

TAUTOLOGY. CONTRADICTION AND CONTINGENCY

A compound proposition that is always true, no matter what the truth values of the propositional
variables that occur in it, is called a tautology.A compound proposition that is always
false is called a contradiction. A compound proposition that is neither a tautology nor a
contradiction is called a contingency.


EXAMPLE
Construct the truth table of p ˅¬p and p ˄¬p. Which statement is Tautology and which is Contradiction?
P  ¬p  p ˅¬p  p ˄¬p
T   F      T          F
F   T      T          F
p ˅¬p is always true, it is a tautology. p ˄¬p is always false, it is a contradiction.
Compound propositions that have the same truth values in all possible cases are called logically equivalent. We can also define this notion as follows.
The compound propositions p and q are called logically equivalent if p ↔ q is a tautology.
The notation p ≡ q denotes that p and q are logically equivalent.
Example
Prove the Absorption Laws by using truth table.
p   q   p˄q    p˅(p˄q)
T   T     T        T
T   F     F        T
F   T     F        F
F   F    F         F
p˄q ≡ p˅(p˄q). Therefore, proven.
p   q    p˅q    p˄ (p˅q)
T   T      T        T
T   F      F        T
F   T      F        F
F   F      F        F
p˅q ≡ p˄ (p˅q). Therefore, proven.
Show that p ˅ (q ˄ r) and (p ˅ q) ˄ (p ˅ r) are logically equivalent using truth table.
p  q  r  p˅q   (p˅q )˅r  q˅r   p˅(q˅r)
T  T  T   T         T           T       T
T  T  F   T         T           T       T
T  F  T   T         T           T       T
T  F  F   T         T           F       T
F  T  T   T         T           T       T
F  T  F   T         T           T       T
F  F  T   F         T           T       T
F  F  F   F         F           F       F
p ˅ (q ˄ r) ≡ (p ˅ q) ˄ (p ˅ r). Therefore, proven.

Inventory

Table: Logical Identities

Untitled222.png
Untitled222.png

Table: Logical Equivalences Involving Conditional Statements.

Table: Logical Equivalences Involving Biconditional Statements.

Untitled222.png
Show that ¬ (p → q) and p ˄¬ q are logically equivalent using the logical identities.

¬ (p → q)
≡  ¬ (¬ p ˅ q)          Logical Equivalence
≡¬ (¬ p)˄ ¬ q         De Morgan law
≡ p ˄¬ q                 double negation law

Inventory

State which rule of inference is the basis of the following argument: “She is a very hardworking girl and
she passed the exam. Therefore, she is a very hardworking girl.
Solution:
Let p be the proposition “She is a very hardworking girl.”
Let q be the proposition “She passed the exam.”
This argument is of the form p ˄ q→ p. This argument uses the simplification rule.

Example
State the conclusion of the following. “If you bring laptop to class, then I will teach you homework.” “If you do not bring laptop to class, then I will go to take breakfast” and “If I go to take breakfast, then I will feel energized.”
Solution:
Let p be the proposition “If you bring laptop to class.”
Let q be the proposition “I will teach you homework.”
Let r be the proposition “I will go to take breakfast.”
Let s be the proposition “I will feel energized.”

Step Reason
1. p → q        Premise
2. ¬q →¬p    Contrapositive of (1)
3. ¬p → r      Premise
4. ¬q → r      Hypothetical syllogism using (2) and (3)
5. r → s        Premise
6. ¬q → s     Hypothetical syllogism using (4) and (5)
DIRECT AND INDIRECT PROOF
The integer n is even if there exists an integer k such that n = 2k, and n is odd if there exists an integer k such that n = 2k + 1. (Note that every integer is either even or odd, and no integer is both even and odd.)


Give a direct proof of the theorem “If n is an odd integer, then n is odd.”

Solution: Note that this theorem states ∀xP ((n) → Q(x)), where P(n) is “n is an odd integer” and Q(n) is “n+2 is odd.”
Assume that the hypothesis of this conditional statement is true, namely, we assume that n is odd. By the definition of an odd integer, it follows that
n = 2k + 1, where k is some integer. We want to show that n+2 is also odd.

n = 2k + 1


+2k)+1
Let +2k= m
(proved)
By the definition of an odd integer, we can conclude that n+2 is an odd integer (it is one more than twice an integer.) We have proved that if n is an odd integer, then n+2 is an odd integer.

Example
Prove that if n is an integer and 3n + 2 is odd, then n is odd.
Solution:
We first attempt a direct proof.
Let 3n + 2 is odd.
3n + 2 = 2k + 1
n=
We cannot proof that if 3n+2 is odd, then n is odd by direct proof.
We next try a proof by contraposition.
p= 3n+2 is odd
q= n is odd
¬q= n is even
Let n is even, we must show that 3n+2 is even.
3n+2 = 3(2k)+2
= 6k+2
= 2(3k+1)
= 2m
n is even, then 3n+2 is even.
This satisfies
Therefore, it is proved that “if 3n+2 is odd, then n is odd”.
Give a proof by contradiction of the theorem “If 3n + 2 is odd, then n is odd.”
Solution:
p = 3n + 2 is odd
q = n is odd
= n is even

Let p ˄¬q are true.
3n + 2 = 3(2k) + 2
= 6k + 2
= 2(3k + 1).
Let m= 3n + 2,
3n +2 = 2m
3n + 2 is even.

 is false, then  is false and q is T. Proved.
Mathematical Induction
Use Mathematical Induction to prove that  for n= 3, 4, 5,…

For
Therefore,
Therefore, it is proved that  n for n = 3, 4, 5