({{, FCM1013: Discrete Mathematics}, {, Propositional Logic &Graph Theory using Wolfram Mathematica}})

Lecturer: Ms. Amy Foong 
04 Oct 2016

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

1. Propositional Logics

2. Graphs

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 “I’m a year-one UTP student”
2. Let q be a proposition that “I’m enrolled to computer science ”

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 “I’m a year-one UTP student”
2. Let q be a proposition that “I’m enrolled to computer science”

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”

p && q

Negation, For Example#2,
Let p be a proposition that “I’m a year-one UTP studentd”
The Negation of the proposition, ￢p is
“It is not the case that I’m a year-one UTP student”

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 VC of UTP, 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 come to the class FCM1013 if and only if you have enrolled.”

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

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

({{Logical name, Mathematica
function, without alias, alias, Math 
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 （Until 1020AM)

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]))

Bonus Hour#1!! （Until 1025AM)

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 freshman”
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 freshman.”

(*Answer*)

Bonus Question
1. Let p be a proposition that “There are other universities in Tronoh”
2. Let q be a proposition that “Study life is fairly good at UTP”
3. Let r be a proposition that “The tuition fee is reasonable”
Please translate the following into a logical expression
“There are no other universities in Tronoh, and study life is fairly good at UTP, but the tuition fee is reasonable.”

(*Answer*)

Submit your answer to http://goo.gl/forms/1Q560tQe2z2F0z8K2

1.3 Truth Tables

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. 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 （Until 1035AM)

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

Run The Codes,
Observe and Understand The Output （Until 1035AM)

(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!! （Until 1045AM)

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/ANMOLoYG5JTaeQre2

2 Graphs And Networks

Some Selected Topics

Graph Plotting in Mathematica

Euler Circuit & Hilmiton Circuit

Graph Plotting in Mathematica

A simple undirected graph, the edge between vertices can be entered as Esc ue Esc.

Graph[{1\[UndirectedEdge]2,2\[UndirectedEdge]3,3\[UndirectedEdge]1}]

A simple directed graph, the edge between vertices can be entered as Esc de Esc

Graph[{1\[DirectedEdge]2,2\[DirectedEdge]3,3\[DirectedEdge]1},VertexLabels->"Name"]

Graph Plotting in Mathematica with Free Form Lingustic & Predictive Inputs

Graph Plotting in Mathematica (Exercise)

Plot the following graph

(*Type your Syntax below*)

What is Euler Circuit?

Can we travel along the EDGES of a graph starting at a VERTEX and returning to it by traversing each edge of the graph exactly once? If yes, this means the graph has an EULER CIRCUIT.

Example : Königsberg Bridge People Königsberg wondered whether they could start at some location in the town, travel across all the bridges ONCE without crossing any bridge twice, and return to the starting point. The Swiss mathematician Leonhard Euler solved this problem.

Mathematica Test For Euler Circuit

MyTest01=Graph[{a\[UndirectedEdge] b,a\[UndirectedEdge] e,a\[UndirectedEdge] d,b\[UndirectedEdge] e,b\[UndirectedEdge] c,d\[UndirectedEdge] c,e\[UndirectedEdge] d,e\[UndirectedEdge] c}]

EulerianGraphQ[MyTest01]

What is Hamilton Circuit?

Can we travel along the edges of a graph starting at a vertex and returning to it while visiting each vertex of the graph exactly once? If yes, this means the graph has a Hamilton circuit.

This terminology comes from a game, invented in 1857 by the Irish mathematician Sir William Rowan Hamilton. The object of the puzzle was to start at a city and travel along the edges of the dodecahedron, visiting each of the other 19 cities exactly once, and end back at the first city.

Example : Hamilton Cycle

Mathematica Test for Hamilton Circuit?

MyTest02=Graph[{a\[UndirectedEdge] b,b\[UndirectedEdge] c,b\[UndirectedEdge] d,c\[UndirectedEdge] d}]

HamiltonianGraphQ[MyTest02]

Bonus Hour#3!! （Until 1110AM)

Plot Graphs and identify the Euler & Halmiton Circuits

MyG01=Graph[{a\[UndirectedEdge]   b,a\[UndirectedEdge] e,b\[UndirectedEdge] e,e\[UndirectedEdge] c,e\[UndirectedEdge] d,d\[UndirectedEdge] c}];
MyG02=Graph[{a\[UndirectedEdge] b,a\[UndirectedEdge] c,a\[UndirectedEdge] d,b\[UndirectedEdge] d,b\[UndirectedEdge] e,c\[UndirectedEdge] d,d\[UndirectedEdge] e}];
MyG03=Graph[{a\[UndirectedEdge]  b,a\[UndirectedEdge] c,a\[UndirectedEdge] e,b\[UndirectedEdge] c,b\[UndirectedEdge] e,c\[UndirectedEdge] e,c\[UndirectedEdge] d,e\[UndirectedEdge] d}];
MyG04=Graph[{a\[UndirectedEdge] b,b\[UndirectedEdge] c,b\[UndirectedEdge] g,c\[UndirectedEdge] d,c\[UndirectedEdge] e,g\[UndirectedEdge] e,e\[UndirectedEdge] f}];

(*Test which ones above are Euler or Halmiton circuits*)

Submit your answer to https://goo.gl/forms/2d6E4dV3xpmKj9qP2

Finding Shortest Path in Hamiltorian Circuit

MyG09=;

{EulerianGraphQ[MyG09],HamiltonianGraphQ[MyG09]}

GraphDistance[MyG09,a,d]

FindShortestPath[MyG09,a,d]

UTP01=FindShortestTour[MyG09]

Finding Shortest Path in Hamiltorian Circuit

HighlightGraph[MyG09,PathGraph[{a,b,c}]]

HighlightGraph[MyG09,PathGraph[UTP01[[2]]]]

Useful Resources

Get your free standalone Mathematica license
http://oemscorp.com/utp-license/

Everything about Discrete Maths in Mathematica
http://reference.wolfram.com/language/guide/DiscreteMathematics.html