“Discrete Structure”
“Logic”
By: Muhammad Bilal
Instructor (Computer Science)
Bacha Khan University Charsadda
Topic: Logic
Outline
• Objectives
• Propositional logic
• Introduction
• Facts
• Syntax
• Operators
• Properties of operators
• Connectives
• Precedence of connectives
• Task
Propositional Logic
Propositional logic
Propositional logic (PL) is the simplest form of logic where all the
statements are made by propositions. A proposition is a
declarative statement which is either true or false. It is a
technique of knowledge representation in logical and
mathematical form.
Example:
It is Sunday.
The Sun rises from West (False proposition)
3+3= 7(False proposition)
5 is a prime number.
Propositional Logic
Following are some basic facts about propositional logic:
Propositional logic is also called Boolean logic as it works on 0 and 1.
In propositional logic, we use symbolic variables to represent the logic, and
we can use any symbol for a representing a proposition, such A, B, C, P, Q, R,
etc.
Propositions can be either true or false, but it cannot be both.
Propositional logic consists of an object, relations or function, and logical
connectives.
These connectives are also called logical operators.
The propositions and connectives are the basic elements of the propositional
logic.
Connectives can be said as a logical operator which connects two sentences.
Propositional Logic
A proposition formula which is always true is called tautology, and it is also
called a valid sentence.
A proposition formula which is always false is called Contradiction.
Statements which are questions, commands, or opinions are not propositions
such as "Where is Kamal", "How are you", "What is your name", are not
propositions.
Propositional Logic
Syntax of propositional logic:
The syntax of propositional logic defines the allowable sentences
for the knowledge representation. There are two types of
Propositions:
Atomic Propositions
Compound propositions
Propositional Logic
Atomic Proposition: A single proposition symbol representing a
sentence which must be either true or false.
Example:
a) 2+2 is 4, it is an atomic proposition as it is a true fact.
b) "The Sun is cold" is also a proposition as it is a false fact.
Compound proposition: Compound propositions are
constructed by combining simpler or atomic propositions, using
parenthesis and logical connectives.
Example:
a) "It is raining today, and street is wet."
b) “Rashid is a doctor, and his clinic is in Kohat."
Propositional Logic
Logical Connectives:
Logical connectives are used to connect two simpler propositions
or representing a sentence logically. We can create compound
propositions with the help of logical connectives. There are
mainly five connectives, which are given as follows:
Negation: A sentence such as ¬ P is called negation of P. A
literal can be either Positive literal or negative literal.
Conjunction: A sentence which has ∧ connective such as, P ∧ Q
is called a conjunction.
Example: Kamal is intelligent and hardworking. It can be written
as,
P= Kamal is intelligent, Q= Kamal is hardworking. → P∧ Q.
Propositional Logic
Disjunction: A sentence which has ∨ connective, such as P ∨ Q.
is called disjunction, where P and Q are the propositions.
Example: “Rashid is a doctor or Engineer",
Here P= Rashid is Doctor. Q= Rashid is engineer, P ∨ Q.
Implication: A sentence such as P → Q, is called an implication.
Implications are also known as if-then rules.
Example: “If it is raining, then the street is wet”.
Let P= It is raining, and Q= Street is wet, P → Q
Propositional Logic
Biconditional: A sentence such as P⇔ Q is a Biconditional
sentence, example If I am breathing, then I am alive
P= I am breathing, Q= I am alive, P ⇔ Q.
Following is the summarized table for Propositional Logic
Connectives:
Propositional Logic
Truth Table:
In propositional logic, we need to know the truth values of
propositions in all possible scenarios. We can combine all the
possible combination with logical connectives, and the
representation of these combinations in a tabular format is called
Truth table.
Following are the truth table for all logical connectives:
Propositional Logic
Propositional Logic
Precedence of connectives:
Just like arithmetic operators, there is a precedence order for
propositional connectors or logical operators. This order should
be followed while evaluating a propositional problem. Following is
the list of the precedence order for operators:
Precedence Operators
First Precedence Parenthesis
Second Precedence Negation
Third Precedence Conjunction(AND)
Fourth Precedence Disjunction(OR)
Fifth Precedence Implication
Six Precedence Biconditional
Propositional Logic
Logical equivalence:
Logical equivalence is one of the features of propositional logic.
Two propositions are said to be logically equivalent if and only if
the columns in the truth table are identical to each other.
Let's take two propositions A and B, so for logical equivalence,
we can write it as A⇔B. In below truth table we can see that
column for ¬A∨ B and A→B, are identical hence A is Equivalent to
B
Propositional Logic
Properties of Operators:
Commutativity:
P∧ Q= Q ∧ P, or
P ∨ Q = Q ∨ P.
Associativity:
(P ∧ Q) ∧ R= P ∧ (Q ∧ R),
(P ∨ Q) ∨ R= P ∨ (Q ∨ R)
Course: Artificial Intelligence CS363- Instructor: ZAIDULLAH, Asst. Prof. Institute of Computing , KUST -- Email: zaidullah@kust.edu.pk
Propositional Logic
Identity element:
P ∧ True = P,
P ∨ True= True.
Distributive:
P∧ (Q ∨ R) = (P ∧ Q) ∨ (P ∧ R).
P ∨ (Q ∧ R) = (P ∨ Q) ∧ (P ∨ R).
DE Morgan's Law:
¬ (P ∧ Q) = (¬P) ∨ (¬Q)
¬ (P ∨ Q) = (¬ P) ∧ (¬Q).
Double-negation elimination:
¬ (¬P) = P.
Student task
Create truth table and verify all the properties of
operators discussed
18 De Morgan’s Laws – 2 - 9a
CS-708
19 Proof – 2 - 16
CS-708
20 Proof – 2 - 16d
CS-708
Topic: Logic
Summary
• Propositional logic
• Introduction
• Facts
• Syntax
• Operators
• Properties of operators
• Connectives
• Precedence of connectives
