({{, FCM1013: Discrete Mathematics}, {, Propositional Logic &Probability with Mathematica}})

Lecturer: Ms. Amy Foong 
March 16, 2016

References
[1] K.H. Rosen, Discrete Mathematics and Its Applications, 7th ed., : McGraw-Hill, 2012.

1. Propositional Logics

2. Equivalence

3. Quantifiers

4. Nested Quantifiers

5. Rules of Inference

1.1 Propositional Logics

Brief Defintion About Proposition

A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either True
or False, but not both. 

For Examples:
1. Kuala Lumpur is the capital of Malaysia. (This is True)
2. 1+1=3 (This is False)
3. UTP is located at Penang. (This is False)

Brief Defintion About Propositional Logic

The area of logic that deals with propositions is called the Propositional Calculus or Propositional
logic. The conventional letters used for propositional variables are p, q, r, s, . . . .

For Examples:
1. Let p be a proposition that “Peter’s mobile phone runs Android”
2. Let q be a proposition that “Peter’s mobile phone has 4GB of Memory”

1.2 Logical Connectives

Brief Defintion About Logic Connectives

We use these logical operators to form new propositions from two or more existing propositions. These logical operators are also called logic connectives.These logic connectives include Negation, Conjunction, Exclusive or, Disjunction, Biconditional, Implication

1. Let p be a proposition that “Peter’s mobile phone runs Android”
2. Let q be a proposition that “Peter’s mobile phone has 4GB of Memory”

p=True;q=True;

Conjunction, For Example#1, 
The Conjunction of these propositions, p ∧ q, is
“Peter’s mobile phone runs Android, AND, it has 4GB of Memory”

q && p

Negation, For Example#2,
Let p be a proposition that “Peter’s mobile phone runs Android”
The Negation of the proposition, ￢p is
“It is not the case that Peter’s mobile phone runs Android”

Not[p]

Disjunction, namely as an inclusive or, For Example#3,
“Students who have taken calculus or computer science can take this class.”

Or[p,q]

Exclusive or, For Example#4, 
“Students who have taken calculus or computer science, but not both, can take this class.”

Xor[p,q]

Implication, 
The statement p → q is called a conditional statement because p → q asserts that q is true
on the condition that p holds. It is also called an implication. For Example#5, 
“If I become the headmaster, then I will lower the tuition fee.”

p=True;q=True;
Implies[p,q]

Biconditional,
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. For Example#6, 
“You can take the flight if and only if you buy a ticket.”

p=True;q=True;
Equivalent[p,q]

You may use built-in Connective functions in Woflram Mathematica, 
the common computer symbols, or mathematical symbols

({{name, function, without alias, alias, symbol}, {negation, Not, !, EscnotEsc, ¬}, {conjunction, And, &&, EscandEsc, ∧}, {exclusive or, Xor,  , EscxorEsc, ⊻}, {disjunction, Or, ||, EscorEsc, ∨}, {biconditional, Equivalent,  , EscequivEsc, ⧦}, {implication, Implies,  , Esc=>Esc, =>}})

For examples,

Not[True]

And[False,True]

Or[True,False, False, True]

Implies[True,And[False,True]]

(True||False)&&True

p\[Implies]q

Run The Codes,
Observe and Understand The Output

Or[1>2,Pi>3]

1>2||Pi>3

1>2∨Pi>3

And[2>1,Pi>3]

2>1&&Pi>3

2>1∧Pi>3

Equivalent[Tan[90],((Sin[90])/(Cos[90]))]

Tan[90]⧦((Sin[90])/(Cos[90]))

Run The Codes,
Observe and Understand The Output

Area01=RegionPlot[x^2+y^2<1,{x,-2,2},{y,-2,2}]

Area02=RegionPlot[x+y>0,{x,-2,2},{y,-2,2}]

Now we graphically show both the areas

Show[Area01,Area02]

Now we may graphically show both the areas, using “OR”

RegionPlot[Or[x^2+y^2<1,
			x+y>0],
{x,-2,2},{y,-2,2}]

Now we may graphically show both the areas, using “Xor”

RegionPlot[Xor[x^2+y^2<1,
			x+y>0],
{x,-2,2},{y,-2,2}]

Now we may graphically show both the areas, using “Implies”

RegionPlot[Implies[x^2+y^2<1,
			x+y>0],
{x,-2,2},{y,-2,2}]

Bonus Hour#1!!

1. Let p be a proposition that “You can access the Internet at UTP”
2. Let q be a proposition that “You are a computer science major”
3. Let r be a proposition that “You are a year-1 student”
Please translate the following into a logical expression
“You can access the Internet at UTP only if you are a computer science major or you are not a year-1 student.”

(*Answer*) p→(q∨¬r)

Bonus Question
1. Let p be a proposition that “Tigers have been seen in the area”
2. Let q be a proposition that “Hiking is safe on the trail”
3. Let r be a proposition that “Rambutan are ripe along the trail”
Please translate the following into a logical expression
“Tigers have not been seen in the area and hiking on the trail is safe, but Rambutan are ripe along the trail.”

(*Answer*)

Submit your answer to http://goo.gl/forms/Y84R36nJs5

1.3 Truth Tables

Brief Defintion About Truth Value & Truth Table

In logic and mathematics, a truth value, sometimes called a logical value, is a value indicating the relation of a proposition to truth. Truth tables can be used to tell whether a propositional expression is true for all legitimate input values, that is, logically valid.

We can use a traditional structural programming like below

p=True; q=True;r=False;
p&&(!q)∨r

Alternatively, we can use the ReplaceAll operator (/.) in Mathematica to quickly perform the substitution.

p&&(!q)∨r /.{p->True,q->True, r->False}

Mathematica has a built-in function for producing a truth table, BooleanTable.

Examples

The Truth Table for Disjunction Or:

Clear[p,q,r]

BooleanTable[p||q,{p,q}]

BooleanTable[{p,q,p||q},{p,q}]

Run The Codes,
Observe and Understand The Output

The Truth Table for Conjunction And:

Clear[p,q,r]

BooleanTable[p&&q,{p,q}]

BooleanTable[p&&q,{p,q}] //TableForm

BooleanTable[{p,q,p&&q},{p,q}] //TableForm

BooleanTable[{p,q,p&&q},{p,q}] //TableView

You convert them to 1/0 Boolean form:

Boole[BooleanTable[{p,q,p&&q},{p,q}]] //TableForm

Run The Codes,
Observe and Understand The Output

(p∨¬q)→(p∧q)

BooleanTable[(p∨¬q)→(p∧q),{p,q}]//TableForm

BooleanTable[{p,q,¬q,p∨¬q,p∧q,(p∨¬q)→(p∧q)},{p,q}]//TableForm

TableForm[
BooleanTable[{p,q,¬q,p∨¬q,p∧q,(p∨¬q)→(p∧q)},{p,q}],
TableHeadings->{None,{p,q,¬q,p∨¬q,p∧q,(p∨¬q)→(p∧q)}}]

Bonus Hour #2!!

Bonus Question
Construct a truth table for the following compound proposition using Mathematica coding similar to the previous slide’s.

(p∨¬q)→q

(*Answer*)

Submit your answer to http://goo.gl/forms/3rCfbF8mqd

Classical Applications Propositional Logic

1) Translating English Sentences
2) Expressing System Specifications
3) Boolean Searches (Like Web Search Engines)
4) Logic Puzzles (Like Sudoku etc)
5) Constructing Logic Circuits (Like hardware control etc)

Bonus Hour #3!!

Bonus Question
Suppose there are signs on two drawers. The sign on the first drawer reads “In this drawer there is money,
and in the other one there is a mouse trap”; and the sign on the second drawer reads “In one of these drawers, there is money,
and in one of them there is a mouse trap.” Suppose that you know that one of these signs is true and the other is false.
In which drawer you can find the money? why?

(*Answer*)

Submit your answer to http://goo.gl/forms/R0ao8hrXP1

2 Propositional Equivalence

Brief Definition About Tautology

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.
Two propositions p and q are logically equivalent if the proposition p↔q is a tautology. 
Mathematica includes a function for checking whether a proposition is a tautology, TautologyQ.

For example, we can visually check that the DeMorgan’s Law ¬(p∧q)≡¬p∨¬q is a propositional equivalence as shown in the following truth table.

TableForm[
BooleanTable[{p,q,p∨q,¬(p∨q),¬p,¬q,¬p∧¬q},{p,q}],
TableHeadings->{None,{p,q,p∨q,¬(p∨q),¬p,¬q,¬p∧¬q}}]

We can also use the following quick test in Mathematica

?TautologyQ

TautologyQ[Equivalent[!(p&&q),!p||!q]]

3.1  Representation of Quantifiers

Brief Definition About Quantification

In logic, quantification is a construct that specifies the quantity of specimens in the domain of discourse that satisfy an open formula. Quantification is used as well in natural languages; examples of quantifiers in English are for all, for some, many, few, a lot, and no.

Universal and Existential Quantifiers

Mathematica represents quantification using the functions ForAll and Exists. 
These functions have the same syntax. In their most basic form, they take two arguments. 
The first argument is the variable being bound by the quantifier, and the second is the expression being quantified.

?ForAll

?Exists

For example, to represent the statement (Subscript[∀, x])P(x), you would enter the following.

ForAll[x,P[x]]//TraditionalForm

Likewise, we can represent the assertion that there exists an x for which the opposite is negative as follows.

Exists[x,-x<0]//TraditionalForm

The ForAll and Exists commands also allow you to express conditions on the bound variable by use of an optional second argument.

For example, to symbolically express the assertion “For all x>0, -x<0” you include the condition x>0 as the second argument and the expression -x<0 as the third argument.

ForAll[x,x>0,-x<0]

You can, in particular, use the condition to specify the domain, or universe of discourse, by asserting that the variable belongs to one of Mathematica’s recognized domains using the Element function.

To assert, for example, that x is a real number, use the Element function with first argument x and second argument Reals, Mathematica’s symbol for the domain of real numbers.

Exists[x,Element[x,Reals],x^2<0]

Mathematica has seven defined domains that you can use: Reals, Integers, Complexes, Algebraics, Primes, Rationals, Booleans.

Run The Codes,
Observe and Understand The Output

ForAll[y,y<1,-y<0]

Exists[x,Element[x,Complexes],x^3<0]

3.2  Truth Value of Quantified Statements

Find the truth value of quantified statement

In addition to symbolically representing quantified statements, Mathematica can determine whether they are true or false.
The Resolve function, applied to an expression involving quantifiers, will eliminate the quantifiers.

For expressions like the ones given previously, the result will be the truth value of the statement.

Resolve[Exists[x,-x<0]]

Resolve[ForAll[x,x>0,-x<0]]

Resolve[Exists[x,x^2<0],Reals]

Note that we obtain a different result by changing the domain.

Resolve[Exists[x,x^2<0],Complexes]

Mathematica has seven defined domains that you can use: Reals, Integers, Complexes, Algebraics, Primes, Rationals, Booleans.

Run The Codes,
Observe and Understand The Output

Resolve[ForAll[x,a x^2+b x+c<0],Reals]

Find sample for existence

For existential quantification, Mathematica can go beyond just finding the truth value and actually give you witnesses for the existence of objects with the desired property. 
This is done using the FindInstance function.

?FindInstance

For example, the statement (Subscript[∃, x])(x^3)=8 is true.

Resolve[Exists[x,x^3==8]]

We can find a witness for this by applying FindInstance with the expression (x^3)=8 as the first argument and the variable as the second variable.

FindInstance[x^3==8,x]

FindInstance accepts two optional arguments. You can ask for more than one witness just by giving the number of instances you would like to find as an argument.

FindInstance[x^3==8,x,3]

You can also restrict the results to a particular domain by giving the domain as an argument. Note that when giving both a domain and a specific number of results, the domain should be the third argument and the number the fourth. Below, we have asked for more instances than exist, so Mathematica just returns the one witness.

FindInstance[x^3==8,x,Integers,3]

Run The Codes,
Observe and Understand The Output

Resolve[Exists[x,-x<0]]

FindInstance[-x<0,x]

Find conditions to make statement true

If a statement has one or more free variables, Mathematica can be used to find conditions on those variables in order to make a statement true. For example, consider the statement (Subscript[∀, x])x·y=0. In this statement, x is bound and y is free. 
The Reduce function can be used to solve for free variables. 
Apply it with the statement as the first argument and the free variable (or list of variables) as the second.

Examples

Reduce[ForAll[x,x*y==0],y]

The result, y=0, means that if the free variable y is replaced by the value 0, then the statement will be true.

Reduce accepts a domain as an optional third argument.

Reduce[Exists[x,x^2==y],y,Reals]

This result means that, restricting all variables to the real numbers, if y is replaced by any non-negative real number, the existential statement (Subscript[∃, x])(x^2)=y will be true. 
Note that if the domain restriction is removed, Mathematica defaults to complex numbers and so there would be no restriction on y.

Reduce[Exists[x,x^2==y],y]

Run The Codes,
Observe and Understand The Output

quan=Exists[{x,y},x≠y&&a x^2+b x+c==0 &&a y^2+b y+c==0]

(*find sample for existance*)
Resolve[quan,Reals]

(*find conditions to make statement true*)
Reduce[quan,{a,b,c},Reals]

4 Nested Quantifiers

In this section we will see how Mathematica can be used to represent statements with nested quantifiers.

Single type quantifier

For statements in which all the quantifiers are of the same kind, you only need to use a single Exists or ForAll with the list of variables surrounded by braces as the first argument.

For example, to represent the statement (Subscript[∀, x])(Subscript[∀, y])(x·y=0)->(x=0∨y=0), we only need one ForAll function with {x,y} as the first argument.

ForAll[{x,y},Implies[x*y==0,x==0||y==0]]

Using the Resolve command, we see that Mathematica recognizes this as true.

Resolve[ForAll[{x,y},Implies[x*y==0,x==0||y==0]]]

Note that since we did not specify a domain, Mathematica uses the default domain based on the context. 
In this case, it uses the complex numbers as its domain, since the content of the statement is about equations. 
In general, the default domain is the largest domain that makes sense in the context.

Run The Codes,
Observe and Understand The Output

ForAll[{x,y},x^2+y^2≥0];
Resolve[%]

5 Rules of Inference

Mathematica can be used to verify the validity of arguments in propositional logic. 
In particular, we’ll write a function that, given a list of premises and a possible conclusion, will determine whether or not the conclusion necessarily follows from the premises. 
An argument is defined to be a sequence of propositions, the last of which is called the conclusion and all others are premises. 

Also recall that an argument (Subscript[p, 1]),(Subscript[p, 2]),…,(Subscript[p, n]),q is said to be valid when ((Subscript[p, 1])∧(Subscript[p, 2])∧⋯∧(Subscript[p, n]))->q is a tautology.
The rule is valid if the premises are true (under an interpretation), then so is the conclusion.
We can use the TautologyQ function to test whether a proposition is a tautology.

For example, we can confirm modus tollens.

TautologyQ[Implies[(!q&&Implies[p,q]),!p]]

TautologyQ[(!q∧(p\[Implies]q))\[Implies]!p]

A Method to

To determine if an argument is valid, we need to: 
(1) form the conjunction of the premises
(2) form the conditional statement that the premises imply the conclusion
(3) test the resulting proposition with TautologyQ.