CS101 - Discrete Math

Robert Batzinger
Dec 2 17

Unit 3 Predicate Logic

Unit 3
Predicate
Logic

\[ \]

Symbolic Logic and Proofs: (3) - Overview
Propositional Logic: (3.1) - Truth Tables, Logical Equivalence, Deductions, Beyond Propositions
Proofs: (3.2) - Direct Proof, Proof by Contrapositive, Proof by Contradiction, Proof by Counter Example, Proof by Cases
Fuzzy Logic: - Handling ambiguities

Symbolic Logic and Proofs

Review: Match the Statements

\[ \begin{array}{|c|c|c|} \hline Symbols & Reading & Type\\ \hline P \land Q & & \\ & Not P & \\ P \lor Q & & Negation\\ &P\quad AND\quad Q & \\ P \implies Q & & Conjugation \\ & P\quad IF\ AND\ ONLY\ IF\quad Q & \\ P \leftrightarrow Q& & Implication\\ &P\quad OR\quad Q & \\ \not P & & Biconditional\\ & IF\quad P\quad THEN\quad Q & \\ & & Disjugation\\ \hline \end{array} \]

Arguments

An argument is a set of statements that draw a conclusion from a hypothesis in the form of a series of premises.

An argument is said to be valid if the conclusion must be true whenever the premises are all true.
An argument is invalid if the conclusion is not valid.
It is possible for all the premises to be true and the conclusion to be false.

Which is invalid?

If Edith eats her vegetables, then she can have a cookie.
Edith eats her vegetables.

\( \therefore \) Edith gets a cookie.

*Florence must eat her vegetables in order to get a cookie.

Florence eats her vegetables.

\( \therefore \) Florence gets a cookie.

Direct Proof

To prove an implication

\[ P \implies Q \]

It is enough to

assume P
deduce Q from P

Squares of x5

Who knows the rule for Squares ending in 5??

Converse and Contrapositive

The converse of an implication

\[ P \implies Q \quad\not=\quad Q \implies P \]

The contrapositive of an implication

\[ P \implies Q \therefore \neg P \implies \neq Q \]

Tautology

A statement that is true base purely on logic

\[ !P \lor Q == P \rightarrow Q \]

Requirements

Validity
Satisfiability
Lack of contradiction

De Morgan's Laws

\[ !(P\land Q) \therefore !P \lor !Q \]

\[ !(P\lor Q) \therefore !P \land !Q \]

Double Negation

\[ !(!P) \therefore P \]

Prove the following

\[ !(P \rightarrow Q) \therefore P\land !Q \]

\[ P\lor Q \rightarrow R \therefore (P \rightarrow R) \lor (Q \rightarrow R) \]

Deduction

Holmes owns two suits: one black and one tweed. He always wears either a tweed suit or sandals. Whenever he wears his tweed suit and a purple shirt, he chooses to not wear a tie. He never wears the tweed suit unless he is also wearing either a purple shirt or sandals. Whenever he wears sandals, he also wears a purple shirt. Yesterday, Holmes wore a bow tie. What else did he wear?

Einstein's Riddle

There are five houses.
The Englishman lives in the red house.
The Spaniard owns the dog.
Coffee is drunk in the green house.
The Ukrainian drinks tea.
The green house is immediately to the right of the ivory house.
The Old Gold smoker owns snails.
Kools are smoked in the yellow house.
Milk is drunk in the middle house.

The Norwegian lives in the first house.
The man who smokes Chesterfields lives in the house next to the man with the fox.
Kools are smoked in the house next to the house where the horse is kept.
The Lucky Strike smoker drinks orange juice.
The Japanese smokes Parliaments.
The Norwegian lives next to the blue house.

The Riddle

Now, who drinks water?
Who owns the zebra?

Note: each of the five houses is painted a different color, and their inhabitants are of different national extractions, own different pets, drink different beverages and smoke different brands of American cigarettes.

Logic Rules

Simple Logic

\[ \begin{array}{rcl} A\lor \neg A &\equiv& T\\ A\lor A &\equiv& A\\ A\lor F &\equiv& A\\ A\lor T &\equiv& T\\ \end{array} \]

AND

\[ \begin{array}{rcl} A\land \neg A &\equiv& F\\ A\land A &\equiv& A\\ A\land F &\equiv& F\\ A\land T &\equiv& A\\ \end{array} \]

Two Element Rules

\[ \begin{array}{rcl} A\land (B\lor \neg B)&\equiv& A\\ A\lor A \land B &\equiv& A\\ A\land (A \lor B)&\equiv& A\\ A\lor B &\equiv& B \lor A\\ A\land B &\equiv& B \land A\\ \end{array} \]

\[ \begin{array}{rcl} \neg (A\lor B) &\equiv&\neg A \land \neg B\\ \neg (A\land B) &\equiv& \neg A \lor \neg B\\ \end{array} \]

Multiple element rules

\[ \begin{array}{rcl} A\lor (B \lor C) = (A\lor B) \lor C &\equiv& B\lor(A\lor C)\\ A\land (B \land C) = (A\land B) \land C &\equiv& B\land(A\land C)\\ A\land (B \lor C) &\equiv& (A\land B) \lor (A\land C)\\ (A\lor B)\land(C\lor D) &\equiv& (A\land C)\lor(A\land D)\lor(B\land C)\lor(B\land D)\\ \end{array} \]

Logical Equivalences (1)

Commutative properties

\[ \begin{array}{rcl} p\lor q&\equiv&q \lor p\\ p\land q &\equiv&q \land p\\ \end{array} \]

Associative properties

\[ \begin{array}{rcl} (p\lor q)\lor r&\equiv&p \lor (q \lor r)\\ (p\land q)\land r &\equiv&p \land (q\land r)\\ \end{array} \]

Logical Equivalences (2)

Distributive laws

\[ \begin{array}{rcl} p\lor (q\land r)&\equiv&(p \lor q) \land (p\lor r)\\ p\land (q\lor r)&\equiv&(p \land q)\lor (p \land r)\\ \end{array} \]

Identity Laws

\[ \begin{array}{rcl} p \lor p &\equiv p \equiv& p \lor F\\ p\land p &\equiv p \equiv& p\land T\\ \end{array} \]

Logical Equivalences (3)

Domination laws

\[ \begin{array}{rcl} p \lor T &\equiv& T\\ p \land F &\equiv& F\\ \end{array} \]

DeMorgan's Laws

\[ \begin{array}{rcl} \overline{p\lor q}&\equiv& \overline{p} \land \overline{q}\\ \overline{p\land q}&\equiv& \overline{p} \lor \overline{q}\\ \end{array} \]

Logical Equivalences (4)

Implications

\[ \begin{array}{rcl} p\implies q&\equiv&\overline{q}\implies\overline{q} \equiv \overline{p}\lor q\\ \end{array} \]

Simplify (1)

\[ \Large (A\lor B)\land (B \lor C)\qquad \]

\[ \begin{array}{l} = (A\land B)\lor (A\land C)\lor (B\land B)\lor (B\land C)\\ = (A\land B)\lor (A\land C)\lor (B)\lor (B\land C)\\ = (A\land B)\lor (A\land C)\lor \left(B\land (T \lor C)\right)\\ = (A\land C)\lor (A\land B)\lor B\\ = (A\land C)\lor \left(B\land (A\lor T)\right)\\ = (A\land C)\lor B\\ \end{array} \]

Simplify (2)

\[ \Large (A\land B)\land(\neg B\lor C)\qquad \]

\[ \begin{array}{l} = (A\land B\land\neg B)\lor (A\land B\land C)\\ = A\land B\land C\\ \end{array} \]

Simplify (3)

\[ \Large B\land(A\lor \neg B)\lor (B\land C)\qquad \]

\[ \begin{array}{l} = (B\land A)\lor (B\land \neg B)\lor (B\land C)\\ = (B\land A)\lor (B\land C)\\ = B\land (A\lor C)\\ \end{array} \]

Simplify (4)

\[ \Large B\land(A\lor C)\lor C\qquad \]

\[ \begin{array}{l} = (B\land A)\lor (B\land C)\lor C\\ = (A\land B)\lor \left(C\land (B\lor T)\right)\\ = (A\land B)\lor C\\ \end{array} \]

Simplify (5)

\[ (A\land B)\lor (A \land C)\lor (B \land C)\lor (A\land B\land C) \]

\[ \begin{array}{l} = A\land \left(B\lor C \lor (B\land C)\right)\\ = A\land \left(B\lor C\land(T \lor B)\right)\\ = A\land (B\lor C)\\ \end{array} \]

Now you try it

\[ (A\land B)\lor (\neg B\land C)\lor(A\land C) \]

\[ \overline{(A\land B)}\land(B\lor C) \]

\[ B\land (A\lor C)\lor C \]

Boolean Arithmetic Representation

Math Symbol	Arithmetic Equiv
\( A\land B \)	\( A \times B \)
\( A\lor B \)	\( A + B \)
\( True \)	\( 1 \)
\( False \)	\( 0 \)
\( \neg(A\lor B) = \neg A \land \neg B \)	\( \overline{A + B} = \overline A \times \overline B \)

Experiment 2: Data from 140K wine reviews

Field	Abbrev	Description	Sample
0	id	Record number	0
1	cntry	Country	France
2	descr	Review	This wine is very…
3	label	Brand name	Martha's Vineyard
4	pts	Reviewer points	83
5	price	Price per litre	20.75
6	prov	Province	California
7	reg_1	Region 1 grown	Oakland
8	reg_2	Alternative Region	Napa Valley
9	variety	Grape variety	Cabernet Sauvignon
10	winery	Manufacturer	Heitz

Histagrams of key parameters

plot of chunk unnamed-chunk-2

plot of chunk unnamed-chunk-3

Parento Distributions

plot of chunk unnamed-chunk-4

plot of chunk unnamed-chunk-5

Logic Predicates Under Study

E = Most expensive wines
L = Least expensive wines
Q = Highest quality wines
P = Poorest quality wines
C = Most common type of grapes
X = Least common type of grapes
V = Made from grapes that create the most expensive wines
I = Made from grapes that create the least expensive wines

Search Criteria

\[ \Large(E\land P \land C) \lor \\ \Large(E\land Q \land X) \lor \\ \Large(L\land Q \land C) \lor \\ \Large(L \land Q \land X)\lor \\ \Large(\neg E\land Q \land C) \lor \\ \Large(\neg E\land Q \land \neg C) \lor\\ \Large(C \land P \land E) \lor\\ \Large(X \land Q \land L)\lor\\ \Large(U \land E)\lor\\ \Large(V \land L) \]

Basic Statistics

Parameter	Mean	Std Dev	min	Q-05	Q-50	Q-95	max	count
Price	33.13	36.31	4.00	10.00	24.00	80.00	2300.00	137235
Price by Grape	22.86	14.29	0.00	8.80	20.00	45.03	150.00	632
Review pts	87.89	3.06	80.00	83.00	88.00	93.00	100.00	150930
Wines by Grape	238.81	1215.43	1.00	1.00	8.00	982.00	14482.00	632

Discrete vs Fuzzy Logic

Discrete Logic Function

# E = Most expensive
def e?
  return (
    @record[5].to_f
       > 79.99)
end 

# L = Least expensive
def l?
  return (
    @record[5].to_f 
       < 10.01)
end

Fuzzy Logic Function

def fuzzyE
  value =
  (@record[5].to_f - 
    10) / 70.00
  if value > 1
    value = 1.00
  elsif value < 0
    value = 0.00
  end
  return value
end

Fuzzy Logic Operations

def fuzzyAND(*fuzzyArray)
  return fuzzyArray.min
end

def fuzzyOR(*fuzzyArray)
  return fuzzyArray.max
end

def fuzzyNEG(val)
  return 1.00 - val
end

Tallies

Wine Parameter	Logic		Tally		Inv		Extreme
Cost per bottle	Dis	E	7323	!E	143607	L	24110
	Fuz		7323		143607		24110
Quality	Dis	Q:	12460	!Q:	138470	P:	12489
	Fuz		12460		138470		12489
Grape Type	Dis	C:	125476	!C:	25454	X:	97
	Fuz		: 125476	!C:	25454	X:	1191
Value by Grape	Dis	V:	4347	!V:	146583	I:	135
	Fuz		1908		149022		174

Directions for this study

Modify dataset.rb for the missing logic functions to determine the counts of wines that meet the criteria and record the time used.
Simplify the logic to the smallest equivalent to reduce the time. Verify that you still get the same results.
Compare the results and determine the degree of improve in the runtime.
Try to see if there are other modifications that can be done to improve efficiency without changing the results.
Run this study again using fuzzy logic and compare differences.
Report your results and the final revised logic in a LaTeX report on Overleaf.

Expected results

Discrete logic

Selected: 9465
Rejected: 141465
Time used:  9.812 sec

Fuzzy logic

Selected: 9172
Rejected: 141758
Time used: 28.859 sec

Propositional Logic: (3.1)

Predicate propositions

Methods

Returns T/F
Normally based on some state of an object
Example: Prime, Odd, Even, Disqualified
Ruby functions: odd?, even?, zero?, empty?, nil?

Attributes

Boolean values
Indicates a characteristic
Example: isHungry?, wasFed?, hasWater?

Proofs

A Proof

Determine if a statement is valid and true

If \( ab \) is an even number, then \( a \) or \( b \) is even.

CONTRAPOSITIVE

if \( a \) and \( b \) are odd: \( ab \) is odd.

\[ \begin{array}{rcl} ab &=& (2k+1)(2m+1)\\ &=& 4km + 2k + 2m + 1\\ &=& 2(km + k + m) + 1\\ \end{array} \]

DIRECT PROOF

if \( a \) or \( b \) is even:

\[ \begin{array}{rcl} ab&=&(2k)b\\ &=&2(kb)\\ \end{array} \]

COUNTER EXAMPLE

if \( ab \) is even and \( a \) and \( b \) are odd:

\[ \begin{array}{rcl} ab = 2n &=& (2k+1)(2m+1)\\ 2n &=& 4km +2k +2m +1\\ n &=& 2km + k + m + {1\over 2}\\ \end{array} \]

DIRECT PROOF

if \( ab \) is even and \( a \) is odd:

\[ \begin{array}{rcl} ab = 2n &=&(2k+1)b\\ 2n &=& 2kb + b\\ 2n - 2kb &=& b\\ 2(n - kb)&=& b\\ \end{array} \]

Direct Proof

Assume \( P \) Explain, explain \( \therefore \) Q

Prove if \( n \) is even, then \( n^2 \) is even.

Prove that if \( a/b \) and \( b/c \) then \( a/c \)

Proof by Contrapositive

Contrapositive

**Assume \( \neg Q \) explain, explain \( \therefore \) \( \neg P \)

Prove if \( n \) is even, then \( n^2 \) is even.

Prove that if \( a/b \) and \( b/c \) then \( a/c \)

Proof by Contradiction

Contradiction

Invalidation by showing an example where the statement is wrong

Prove if \( n \) is even, then \( n^2 \) is even.

Prove \( n^2 - n + 41 \) is not always prime

\( n \)	1	2	3	4	5	6	7
\( n^2-n+41 \)	41	43	47	53	61	71	83

\( n=41 \) is not a prime

Some examples

Prove that \( n^3 - n \) is always even.
Prove that \( n^3 - n \) is divisible by 3

Proof by Counter Example

Counter Example

Proof by showing that contradictions cannot exist.
Disproving by showing a contradiction

Prove that not all lines are perpendicular to each other.

Proof by counter example

\[ \begin{array}{rcl} f_1(x) = 3x + 7\\ f_2(x) = 2x - 3\\ \end{array} \]

graph1

Perpendicular

graph1

Proof by Cases

Prove by showing that all cases are true

Prove that \( n^3-n \) is always even

Proof by cases

Even numbers

\[ \begin{array}{l} n^3 - n \\ \quad = (2k)^3 - 2k\\ \quad = 8k^3 - 2k\\ \quad = 2(4k^3 - k)\\ \end{array} \]

Odd numbers

\[ \begin{array}{l} n^3 - n \\ \quad = (2k+1)^3 - (2k+1)\\ \quad = 8k^3 + 12k^2 + 6k + 1 - 2k - 1\\ \quad = 8k^3 + 12k^2 + 4k)\\ \quad = 2(4k^3 + 6k^2 + 2k)\\ \end{array} \]

Some observations: x = n^3 - n

n    x       x/12

1    0       0 
2    6       0.5 
3    24      2 
4    60      5 
5    120     10 
6    210     17.5 
7    336     28 
8    504     42 
9    720     60 
10   990     82.5

n    x       x/12

11   1320    110 
12   1716    143 
13   2184    182 
14   2730    227.5 
15   3360    280 
16   4080    340 
17   4896    408 
18   5814    484.5 
19   6840    570 
20   7980    665

Fuzzy Logic

Value
Fuzzy Complement
Fuzzy Union
Fuzzy Intersection

Fuzzy Value

Level of membership on a scale of 0 - 1

Fuzzy Complement

Collection of the inverse of membership calculated as 1 minus the membership

Fuzzy Union

Collection of the maximum degrees of membership

Fuzzy Intersection

Collection of the minimum degrees of membership

Solutions (1)

\[ \Large (A\land B)\lor (\neg B\land C)\lor(A\land C)\qquad \]

\[ \begin{array}{l} = (A\land B)\lor (\neg B\land C)\lor(A\land C)\land(\neg B\lor B)\\ = (A\land B)\lor (\neg B\land C)\lor(A\land\neg B\land C)\lor (A\land B\land C)\\ = (A\land B)\land(T \lor C)\lor (\neg B\land C)\land(T\lor A)\\ = (A\land B)\lor (\neg B\land C)\\ \end{array} \]

Solutions (2)

\[ \Large \overline{(A\land B)}\land(B\lor C)\qquad\qquad \]

\[ \begin{array}{l} = (\overline{A}\lor \overline{B})\land(B\lor C)\\ = (\overline{A}\land B)\lor (\overline{A}\land C)\lor (\overline{B}\land B)\lor (\overline{B}\land C)\\ = (\overline{A}\land B)\lor (\overline{A}\land C)\lor (\overline{B}\land C)\\ \end{array} \]

Solutions (3)

\[ \Large B\land (A\lor C)\lor C\qquad \]

\[ \begin{array}{l} = (B\land A)\lor (B\land C)\lor C\\ = (B\land A)\lor (B\lor T)\land C\lor C\\ = (B\land A)\lor C\lor C\\ = (A\land B)\lor C\\ \end{array} \]

Solution for Einstein

Quality	H1	H2	H3	H4	H5
Color	yellow	blue	red	ivory	green
National	norway	ukrain	england	spain	japan
Cigarette	kools	chesterfield	OldGolf	LuckyStrike	Parliament
Drink	WATER	tea	milk	orangeJuice	coffee
Pet	fox	horse	snails	dog	ZEBRA

CS101 - Discrete Math

Unit 3 Predicate Logic

Unit 3PredicateLogic

Contents

Symbolic Logic and Proofs

Review: Match the Statements

Arguments

Which is invalid?

Direct Proof

Squares of x5

Converse and Contrapositive

Tautology

Requirements

De Morgan's Laws

Double Negation

Prove the following

Deduction

Einstein's Riddle

The Riddle

Logic Rules

Simple Logic

Two Element Rules

Multiple element rules

Logical Equivalences (1)

Logical Equivalences (2)

Logical Equivalences (3)

Logical Equivalences (4)

Simplify (1)

Simplify (2)

Simplify (3)

Simplify (4)

Simplify (5)

Now you try it

Boolean Arithmetic Representation

Experiment 2: Data from 140K wine reviews

Histagrams of key parameters

Parento Distributions

Logic Predicates Under Study

Search Criteria

Basic Statistics

Discrete vs Fuzzy Logic

Fuzzy Logic Operations

Tallies

Directions for this study

Expected results

Discrete logic

Fuzzy logic

Propositional Logic: (3.1)

Predicate propositions

Proofs

A Proof

Direct Proof

Direct Proof

Proof by Contrapositive

Contrapositive

Proof by Contradiction

Contradiction

Some examples

Proof by Counter Example

Counter Example

Proof by counter example

Perpendicular

Proof by Cases

Proof by Cases

Proof by cases

Some observations: x = n^3 - n

Fuzzy Logic

Fuzzy Value

Fuzzy Complement

Fuzzy Union

Fuzzy Intersection

Solutions (1)

Solutions (2)

Solutions (3)

Solution for Einstein

Unit 3
Predicate
Logic