Comp231 Logic 231219

 Sadat Academy

Discrete Structures

Instructor: Prof. Dr. Hamed Nassar

 Logic
Dr. Hamed Nassar, Suez Canal Univ. 1

Textbook: “Discrete Mathematics and its
Applications”, 8th ed, Kenneth Rosen, McGraw Hill, 2019
Reference Books:
• Mathematical Structures For Computer Science, 7th ed, Judith Gersting,
Freeman, 2014.
• Discrete Mathematical Structures, 6th ed, Sharon Ross, Bernard Kolman,
Robert Busby, Pearson, 2015.
Dr. Hamed Nassar, Suez Canal Univ. 2

Logic: Manipulates Declarative Statements
 Declarative Statement: A statement that can be judged True or False, either
directly (proposition), or after info is supplied for some unknown in the
statement (predicate).
 Ex Non- Declarative Statements (as they cannot be judged: T or F)
Prof. H. Nassar, BAU

Logic: Manipulates Declarative Statements
 Ex Declarative Statement :
◦ Propositions: 2+2=3, 3>2, River Nile is longer than 50 km
 Here, first is F, second is T, third is T
◦ Predicates: x+2=3, x>2, River x is longer than 50 km
 Here, no one can tell whether a statement is T or F unless further info
on x is given, in which case the predicate becomes a proposition. This
info can be by either direct substitution for x (which is not interesting),
or qualifying x (which is the subject of predicate logic.) For the first
predicate, if we substitute x=1, the resulting proposition is T. On the
other hand, if we assume that x belongs to the set of real numbers, and
we qualify the predicate universally, the resulting proposition: (for all x in
R, x+2>3) is F. For the last predicate, let us assume x to belong to the
set of all rivers in the World. Then, if we qualify the predicate universally,
the resulting proposition (all rivers in the world are longer than 50 km) is
F, whereas if we qualify it existentially, the resulting proposition (there
exists some rivers in the world that are longer than 50 km) is T.
 Conclusion: Logic is thus two types, Propositional and Predicate.
Part I
Propositional Logic

Propositional Variables & their Values,
and logical operators
 New (compound) propositions can be produced from

existing (simple) ones, using logical operators.
 Logical operators: Just as there are arithmetic

operators (+, -, /, *, etc.), there are logical operators
such as AND, OR, etc.

NOT (Negation) Operator
 Definition: Let p be a proposition, then
Truth Table of “NOT”
 Example: p=At least 10 inches of rain fell in Beirut yesterday

 ¬p= Less than 10 inches of rain fell in Beirut yesterday
 Sometimes ¬p is written p’

AND (Conjunction) Operator
 Definition:
Truth Table
 Example:

OR (Disjunction) Operator
 Definition:
Truth Table
 Example:

XOR Operator
 Definition:
 Example: If we replace
OR, in the previous example
by XOR, then we have
Today it is either Friday or it is raining

Implication: if p then q, q if p = p only if q
p: hypothesis, premise, antecedent , q=conclusion, consequence
 Definition:
 Truth Table:
 Note that the implication is false only
when p is true and q is false, and is true otherwise.
 Other forms of implication:

Implication: q if p = p only if q
p: hypothesis, premise, antecedent – q=conclusion, consequence
 TT Explanation:
 Think of a teacher t, telling
his student s:
You will pass the course if you solve at least three problems.
That is: p=solve at least 3 problems and q= pass the course
We have these 4 scenarios after end of the course:
 Student solves 4 problems (p=T) and passes (q=T):
Student HAPPY. . He got what he deserves
 Student solves 2 problems (p=F) and does not pass (q=F):
Student HAPPY . . He got what he deserves
 Student solves 2 problems (p=F) and passes (q=T):
Student HAPPY . . He benefited from the teacher’s generosity
 Student solves 4 problems (p=T) and does not pass (q=F):
Student SAD. . He did NOT get what
Prof. H. heBAU
Nassar, deserves
If (hypothesis[proposition]), (conclusion[proposition])
 Example:
 “if” in computer programs:
is false. We will see later that the computer’s if is equivalent in logic to iff.

IF: in math and in English - Pk
 Pk: The cause-effect connotation of the “if” of ordinary English may be missing in
the “if” of mathematical logic. The latter is purely of a formal structure.
 Mathematical: (conclusion[proposition]) IF (hypothesis[proposition]),
 English : (effect[result]) IF (cause[predicate]),
 Take the example of: you will pass the exam IF you study well -> (pass IF study)
hypothesis is sufficient for conclusion, and conclusion is sufficient for hypothesis
Logic: study sufficient for pass: verifiable (via TT), pass necessary for study: verifiable (via TT)
English: study sufficient for pass : understandable as study precedes passing, thus causes it.
pass necessary for study : NOT understandable as passing does not precede study to be
necessary for it Prof. H. Nassar, BAU
Example on the variations of “if”
 if you eat well, your health improves = your health improves if you eat well
 Eating well is sufficient for your health improvement
 you had eaten well, only if your health has improved
 Your health improvement is necessary to judge you have eaten well
This last statement is confusing if it is read with the “English” usage in mind, as
health improvement follows eating well. In English, a is necessary for b, if a
precedes b. Here, health improvement does not precede eating well, but rather
follows it. So, where is the catch? The catch is that in logic, we have in mind
only the truth values of the propositions considered in the TT of “IF”, i.e.:
Eating well is true (in the TT), only if your health improvement is true (in the TT)
a = eating well b = health improvement if a then b (a only if b)
T T T
T F F
F T T
F F T
Excluding the 2nd case (where the whole IF statement is False), of all the cases where the
whole IF statement is True, the only case where a is True is only if b is True.
Converse, Contra-positive, and Inverse
 Proposition Equivalence:
 Truth Table of Converse, Contrapositive, and Inverse:

Proposition Contrapositive Converse Inverse
p q pq q  p qp p  q
T T T T T T
T F F F T T
F T T T F F
F F T T T T
 As can be seen, only the Contrapositive is Equivalent to the original implication
Contrapositive
 As can be seen from the table, the TT of the
contrapositive of a proposition is the same as that of
the proposition itself, which means they are both
equivalent.
 That is, if p  q is a proposition, then its contrapositive, denoted by q  p, has
the same truth table, i.e. is equivalent
 Example:
“If you eat well, your health will improve”
IS EQUVALENT TO its contrapositive
“If your health does not improve, you have not eaten well”

Converse
 As can be seen from the table, the TT of the converse is
different from that of the proposition, which means
they are not equivalent.
 That is, if p  q is a proposition, then its converse, denoted by q  p, does not
have the same truth table, i.e. not equivalent
 Example:
IS NOT EQIV TO its converse
“If your health improves, you are have eaten well”

Inverse
 As, can be seen from the table, the TT of the inverse is
different from that of the proposition, which means
they are not equivalent, but is the same as that of the
converse, which means that the inverse and converse
are equivalent.
 That is, if p  q is a proposition, then its inverse, denoted by p  q, does not
have the same truth table, i.e. not equivalent
 Example:
IS NOT EQUIVALENT TO its inverse
“If you do not eat well, your health will not improve”

Bi-Condtional or Bi-Implication
 Definition:
 Note that a biconditional a iff b is equiv

 to (a if b) ˄ (b if a).
Truth Table:
 Example:

Implicit IFF in natural language
 Using iff in conditioning, tells that the condition is indispensible and is unique. That is,
nothing else will achieve the occurrence of the result. The condition a if b, is not as
strong. It is true here that b will still achieve the occurrence of a, but it is dispensable
and other conditions (or even none) can achieve theProf. occurrence of the a.
H. Nassar, BAU
An informal word on iff
 A if B: means B is sufficient for A
 but also means that A can be true without B being true
(i.e. B will do it but can also be dispensed with)
 That is why we add only if to emphasize the
indispensability of B. Thus
 A iff B: means B will do it and it is the only thing that
will do it (cannot be dispensed with).
 Ex: Ahmed will pass the exam if he studies
(study is a DISPENSIBLE condition, i.e. Ahmed can pass without studying!)
 You can look at the “only if”, in “iff”, as a sort of “insistence”,
much like the “only one” in “one and only one”.

Evaluating TT for complex propositions
 Ex:
 Precedence of Logical Operators:

If more than one logical operators
are involved in the same equations,
they are executed based on the following
precedence:
Translating English Statements into Propositional
variables and logical Connectives
 Ex:

Translating English Sentences
 Ex:
 Alternative: r = ride roller coaster r’ = does not ride

t = four feet or more t’ = under four feet
o = older than 16 yrs old o’ =16 years or younger
(Always, look for the KEY-words when looking for symbols, and give symbols to what you feel
positive, and then represent the negative by the negation)
r’ if (t’ ^ o’) = (t’ ^ o’) ! r’
Note, we can manipulate it using D’Morgan’s law to get
if (t v o)’ then r’ = if r then (t v o) = r Prof.
! H.(tNassar,
v o)BAU(contrapositive)
System Specification in H & S
 Ex:
 s = automated reply is sent s’ = automated reply is NOT sent

 f = file system is full
 Then the specification above is: If f then s’, i.e.
f ! s’
 HW: P. 16 . . . : Solve 1, 4, 13, 20, 22, 33, 36, 45.

System Specification in H & S
 Ex:
 Alternative: s = diagnos msg stored in buffer, r = diagnos msg retransmistted

From specs, we have s v r =T (1)
 s =T (2)
s ! r =T (3)
From, (2) we have s = F. Using s = F in (1), then r = T.
Finally, using s = F and r = T in (3), we get T as it should, which means the specs
are consistent.
Translating, another example
 Alternative: A says “B is a knight” (1), B says “we are opposites” (2)

 We have 4 possibilities: Ag (A is a knight), Av (A is a knave)
Bg (B is a knight), Bv (B is a knave)
by (1) by (2)
 First, assume Ag = T ! Bg = T ! Ag=F, contradicting the assumption
by (1) by (2)
 Now, assume Av = T ! Bv = T ! Av=T, consistent
Prof. H. Nassar, BAUwith assumption
Propositional Equivalences
 Definition:
 Ex:

Logical Equivalence
 Def:
 Note 1: See the word “compound”, i.e. equivalence is between comp prop
 Note 2:  and  and are not the same, but  and  are.
 Note 3: Logical equivalence is usually established using TT.
 Ex. (De Morgan’s Law):

Clarification: link between iff, tautology and logical equivalence
 Tautology: is defined for ONE compound proposition (as it

would make no sense for a simple prop) and has no symbol.
 If TWO compound propositions p and q are connected by the
dual implication (iff) connective, whose symbol is $ , they
become ONE (even more compound) proposition, and then if
that (heavily compound) proposition is a tautology (i.e. is always
true no matter what the values of p and q are), then p and q are
said to be logically equivalent.
 That is, logical equivalence is defined for TWO compound
propositions connected by a bimpilication, and has the symbol
, or ´ . That is,
p , q is the same as p ´ q

Equiv. vs. tautology
 The easiest way to show the logical equivalence of two compound propositions is to
connect them by a biconditional and show, USING a TT, that the resulting compound
proposition is a tautology. Or, simply show that the two columns in the TT of the two
propositions on the sides of the biconditional are the same.
 In essence, we speak of tautology and logical equivalence when we have two
compound propositions. We speak of tautology if we would like to emphasize the
“biconditional iff” linkage between the propositions and how it holds always true
regardless of the values of the variables involved. On the other hand, we speak of
logical equivalence if we would like to emphasize the (truth table) identity of the two
propositions for all values of the variables involved.
 Example: Show if p = r ˅¦s and q = ¦r ˄s are logically equivalent.
 Sol: We won’t insert a biconditional and show the tautology. Rather, we will just show
that the two columns in the TT for the two propoisions are the same.
r s ¦r ¦s p = r ˅¦s q = ¦r ˄s
T T F F T F
T F F T T F
F F T T T F
F T T F F T
 Since the last two columns are not the same, the two props
Prof. are BAU
H. Nassar, NOT logic equivalent.
Logical Equiv
 Ex:
 Ex:

Important Logical Equivalences

Proving Equivalances without TT
 The associative law is about order of carrying out the
operations invloved:
 Ex:

Using De Morgan’s Law
 Ex:

Proving tautologies without TT
 Ex: GOOD
 HW: p. 28 . . . : 10, 17, 25, 33

P
 E

P
 E

P
 E

P
 E

Good Logical equivalences
 E

P
 E

P
 E

P Note in “g”:
 1- If we remove the implication the statement would mean that
there is at least one (not exactly one) that is loved by
everybody.
 2- The implication removes this possibility, how? It says: For
every person z, if z is loved by any person w, then that z is really
x (i.e. nobody is loved, but x)
 Note in “h”:
 1- If we remove x≠y, then x and y can be the same person
(recall that in math, as in programming, we write the symbos
without knowing what the substitutions will be)
 2- If we remove the last part (z(…)), then Lynn can be liking
many pairs x and y (recall that  means “at least one”)
 3- If we remove the middle part (Lynn loves x and Lynn loves y),
and retain the first and last parts, it will mean that that there
are two different persons x and y, and if Lynn likes anybody it
P
 Note in “j”:
 1- Why iff, not if (i.e if x loves anyone, it is x himself)? I think
the if is possible. So this is a little vague.
 2n ¬ ∧ ∨ ⇒             ≠  ⇔ ¬  ≡ (A1 ∨
Am ) (A1∨A2)
 Example 7 Rosen, p. 54: There is a multiplicative inverse for
every non-zero real number.
 Me: x y (x ≠ 0  xy=1): This is wrong since if we remove
temporarily the “x”, we will find an implication is in the
scope of  (an implication is ok in the scope of ).
 Bk: x (x ≠ 0  y(xy=1)): This is correct since the premise
of the implication is actually a restriction of the domain (that
is, it is the alternative of saying  x ≠ 0 y(xy=1)). Recall that
the restriction of domain is  for  and ∧ for 

P
 I am going to run an anti virus application on my PC.
What should I say:
◦ A- The PC is virus free if the application does not detect a
virus.
◦ B- The PC is virus free only if the application does not
detect a virus.
 I am going to compile a C-program I just wrote.

What should I say:
◦ A- The program syntax is good if the compiler does not
detect errors.
◦ B- The program syntax is good only if the compiler does
not detect errors.
Part II
Predicate Logic

II - Predicate Logic (a)
 You can think of propositional logic as the logic of the “known”. That is, it is
about propositions, which are statements that can be decided T or F. An
example is the statement “Ahmed likes coffee” is a proposition.
 On the contrary, you can think of predicate logic as the logic of the
“unknown”. That is, it is about predicates, which are statements that can
NOT be decided T or F, unless some “intervention” is made. An example is the
statement “x likes coffee” is a predicate, where x is an “unknown” belonging
to a domain which is “known”. For example, x may belong to the set of
friends F={Ahmed, Ali, Said}
 The intervention that can transform a predicate into a proposition is one of
two things: Either substitution with a value (from the domain) or
quantification (which picks all of part of the elements of the domain). Thus
we can transform the mentioned predicate by either saying “Said likes coffee”,
or there exists a friend that likes coffee, or all of my friends like coffee.
 Predicate logic is mainly about predicates that are made propositions by the
latter– namely by quantification, i.e. “for all” or “there exists”.
 Both types of logic, propositional (about knowns) and predicate (about
unknowns) complement each other, and in a mathematical deduction both
are typically used alternately. Prof. H. Nassar, BAU
II - Predicate Logic (b)
 Propositional logic is intended for statements whose truth
values are already known (called propositions). Specifically, it is
used to calculate the truth value of a compound proposition
(made up of many propositions connected by such connectives
as: and, or, not, conditional, bi-conditional) given the truth
values of its constituent propositions.
 It says nothing of statements relating properties to objects.
Specifically, it has little or no ability to tell if a “property”
applies to all objects in a given set, or if there exists an object
(or more) in a set where a property applies. For this we need
predicate logic and its two quantifiers: universal and existential.
 So, in predicate logic we may give a statement like: for every
real numbers x>1, x2>x, and conclude from it an infinite
number of true propositions, e.g. 42>4, 52>5, etc. This vehicle
is crucial in the development of mathematical theory.
Predicates
 Statement: x is greater than 3

x : Subject
is greater than 3 : predicate (property of the subject)
Statement: x is greater than 3
 But, informally, the whole statement is looselyProf.
called a “predicate”.
H. Nassar, BAU
Predicate to Proposition, and notation
 P(x): P is a predicate and x is the subject, or P is a propositional

function and x is the variable.
 Ex:
 Ex (Predicate Q, in two variables x,y):

Predicate Logic
 Ex:

Converting a Predicate into a Proposition
 Recall:
◦ Proposition: A statement that can be either True of False
◦ Predicate: A statement with a variable, whose Truth or
Falsehood can be decided only if the variable is determined.
 Note that converting through substitution is not interesting,

as its validation is immediate, whereas conversion through
qualification is the interesting endeavor, as it can be
challenging to validate and really is not immediately
comprehensible. Prof. H. Nassar, BAU
Predicate Calculus:
Manipulating predicates with quantifiers
 Intro:

Quantifiers
 Universal, meaning: for All,  (inverted A). Reads also: for
every, for each, for any, for arbitrary, given any, … However,
“for any” had better be avoided as the meaning of “any” could
be confused between “every” and “some” (used in existential
quantifier)
◦ Ex: x, x2>0
◦ Syntactically, this statement is correct. Semantically, though, to judge its
truth, we need to know the domain of x, called the domain of discourse or
the universe domain. If the domain is the set of real numbers, then the
statement is false, as there exists x (namely x=0) for which it does not
hold. But if the domain is the set of natural numbers, then it is true
 Existential, meaning: there Exists,  (inverted E). Reads also:
for some, for at least one, there is.
◦ Ex: x, x2  0 (The negation of the statement above)
◦ Syntactically, this statement is correct. Semantically, though, to judge its
truth, we need to know the domain of x. If it the set of real numbers, then
the statement is true (as x=0 satisfies the statement.)
Quantifiers: Notes & precedence
 The set of variables covered by a quantifier is called its scope.
 A variable in that set is said to be bound by the quantifier; else
it is free.
 When the elements of the domain of an universal quantifier can
be listed, e.g. x1, x2, …, xn, the statement  x P(x) is equivalent
to the conjunction: P(x1) ∧ P(x2) ∧ . . . ∧ P(xn) because the
conjunction is true if they are all true.
 If the domain of a universal quantifier is empty, the quantified
statement is true, as there is no element that gives false.
 When the elements of the domain of an existential quantifier
can be listed, e.g. x1, x2, …, xn, the statement x P(x) is
equivalent to the disjunction: P(x1) ∨ P(x2) ∨ . . . ∨ P(xn)
because the disjunction is true if there is at least one true.
 If the domain of an existential quantifier is empty, the quantified statement is
false, as there is no element that gives true.
 Quantifiers have precedence over all propositional logic operators. Thus,
Quantifiers with restricted domains
 A quantifier’s domain can be stated in words outside the
quantified statement, or in shorthand notation in the statement.
 Ex 1: We can either say
◦ 1) x (x2 >0), where the domain of x is the set of -ve real numbers, or
◦ 2) (x<0) (x2 >0)
 Ex 1: We can either say
◦ 1) x (x2 = 2), where the domain of x is the set of +ve real numbers, or
◦ 2) (x>0) (x2 = 2), or
 The restriction of a universal quantification is the same as the
universal quantification of a conditional statement, and that of
an existential quantification is the same as the existential
quantification of a conjunction
 Ex 1’: We can say x (x<0 ⇒ x2 >0) instead of (x<0) (x2 >0)
Interpreted: every negative value x, i.e. x<0, will have a positive square, i.e. x2 >0.
 Ex 2’: We can say x (x>0 ∧ x2 = 2) instead of (x>0) (x2 = 2)
Interpreted: there exists a value x with the properties: x>0 and x2 = 2
Domain Restriction: 3 methods
 A quantifier’s domain can be restricted in 3 ways:
◦ in words outside (after) the quantified statement
◦ in notation (if mathematical) next to the quantifier
◦ within the quantified statement, either in notation if
mathematical or as a predicate (defined a priori) if
mathematical or verbal, as the premise of an implication if the
quantifier is  or as a cojunctive property if it is .
 Ex 1: Use the 3 methods above to express “the
square of every negative number is positive.”
◦ x (x2 >0), where the domain of x is the –ve reals.
◦ (x<0) (x2 >0) (Read: for all x <0, x2 >0, OR Every negative
number has a positive square)
◦ x (x<0 ⇒ x2 >0) (Read: for all x, if x<0 then x2 >0, OR for
all x, if x is negative, then its square is positive)
Domain Restriction: 3 methods
◦ x (x2 = 2), where the domain of x is the set of +ve reals, or
◦ (x>0) (x2 = 2), or
◦ x (x<0 ⇒ x2 >0) instead of (x<0) (x2 >0)
Interpreted: every negative value x, i.e. x<0, will have a
positive square, i.e. x2 >0.
◦ Ex 1: Use the 3 ways to express the statement that
there is a root for 2 in the positive reals.
◦ x (x2 = 2), where the domain of x is the set of +ve reals, or
◦ (x>0) (x2 = 2), or
◦ x (x>0 ∧ x2 = 2)
The last one is read: there exists a value x with the
properties: x>0 and x2 = 2 OR there exists a number x
such that (x>0 ∧ x2 = 2) is true.
 Usually, we use “such that” following  (not ), saying “there exists x such that P is true”
D
 Let F(x) denote “citizen x” speaks French.
Express in predicate logic the statement “All
Lebanese people speak French”, using all three
methods of domain restrictions. Define the
domain of discourse in each method.
 Repeat for the statement “There exists a
Lebanese that speaks French”.
Universal Quantifier
 Def:
 domain = domain of discourse = universe of discourse

 As in mathematical functions, the domain of a quantification should always be
specified; otherwise the statement is not defined.
 Meaning changes of a quantifiction changes when the domain changes.
Quantification
 Ex:
 If domain of a UQ is empty, then the quantification is true. It is like an

empty product equalling 1 in arithmetic.
 Same: For all, all of, for each, for arbitrary, given any,Prof.
forH.any- butBAU
Nassar, avod latter two.
Quantification
 Ex:
 It is better to disprove a universal quantification by showing a

counterexample (one x for which P(x) is false)
Existential Quantifier
 This note is valid also in math function where the

domain must be specified to complete the definition of
the function. Its absence makes the function
meaningless, and its change changes the function.

 Ex:
 Ex:

Quantifiers with restricted domains:
 Ex:
 For all there exists – NOT - AND OR - if iff.

Binding Variables and quantifier’s scope

Logical Equivalences involving quantifiers
 Def.:
 Ex.:
To show the equivalence, we need to show that these two implications are true:
·x(P(x)¥Q(x)) ! ·xP(x)¥·xQ(x)), and
·xP(x)¥·xQ(x)) ! ·x(P(x)¥Q(x))
We will use now a “standard” proof technique commonly used in such situations.
To prove the first, assume that ·x(P(x)¥Q(x)) is true and let a be a point in the domain.
Then, P(a)¥Q(a)) is true, which implies (from the properties of ¥) that P(a) is true and Q(a) is true.
And since a is any point in the domain, then ·xP(x)¥·xQ(x)) which is the first part.
To prove the second, assume that ·xP(x)¥·xQ(x) is true and let a be a point in the domain.
Then, P(a) is true and Q(a) is true, which implies (from the properties of ¥) that P(a)¥Q(a)is true.
And since a is any point in the domain, then ·x(P(x)¥Q(x))Prof.
which is the second part.
H. Nassar, BAU
Negation of logical quantifiers
 Each of the two logical quantifiers can be negated.
Actually, each quantifier is used in the negative of
the other. Namely, the negative of “For all x P(x)”
is “There exist x ¦P(x).” and vice versa. The table
below details on this.

Negating quantified expressions
 Ex: Write the logical expression and its negation for the following statement:
“Every student in the class has taken calculus.”
 Sol.:
 Let x be a student in the class, and Q(x) be the propositional function representing
the predicate “x has taken calculus.”
 Then, the statement can be expressed logically as
·xQ(x)
 The negative of this expression is
¦(·xQ(x)) = ¸x¦Q(x)
which when translated into English gives,
“There exists some student in the class that has not taken calculus.”
 Problem.: Write the logical expression and its negation for each of the following
two statements:
“There is an honest politician”,
“all Arabs eat chicken..”
Homework: Problems: 4, 6, 10, 14, 20, 24, 30, 32, 34, 36
 Ex: (argument = premises + conclusion)

English Statements and Specifying domains as predicates
 As we have seen, quantifiers work on domains. The truth of a
quantified statement depends on the definition of the domain of
discourse.
 Ex: Consider the following statements (which make an argument):
◦ All lions are fierce (premise 1)
◦ Some lions do not drink coffee (premise 2)
◦ Some fierce creatures do not drink coffee (conclusion)
 Here we can define two domains one for lions and one for fierce
creatures, and proceed accordingly. However, the statements
would have no tying bonds. A better approach is to define the
domains as predicates, as follows.
 Let P(x) and Q(x) denote that x is a lion and fierce creature,
respectively, and let R(x) denote x drinks coffee. Then,
◦  x (P(x) ⇒ Q(x)),  x (P(x) ∧ ￢ R(x)),  x (Q(x) ∧ ￢ R(x))
◦ As can be seen, the last statement (conclusion) is a consequence of the
previous two (premises), and this can be shown by a derivation.
Predicate logic and English
 Ex: Translate into predicate logic the English statment
Every student in this class has studied calculus
 Letting P(x) denote that student x has studied calculus, then the
above statement expressed in predicate logic as one of:
◦ Defining the domain as the set of all students in class, we say:  x P(x)
◦ Defining the domain as the set of all students (in the world), and letting
C(x) denote the statement “student x in the class under consideration”, we
say:  x (C(x) ⇒ P(x)), which would mean “every student (in the world) that
is in the class has studied calculus.
◦ Note that we could not say:  x (C(x) ∧ P(x)) as it would mean that “Every
student (in the world) is in the class and has studied calculus”, which is of
course ridiculous.
 Using a two-variable predicate Q(x,y) to denote that student x has
studied subject y, where y assumes names such as calculus,
physics, etc., then the above statement in predicate logic is:
◦ Defining the domain as the set of students in class, we say:xQ(x, calculus)
Predicate logic and English: Ex1
Some student in this class has visited Mexico
 Letting M(x) denote that student x has visited mexico, then the
above statement expressed in predicate logic as one of:
◦ Defining the domain as the set of all students in class, we say:  x M(x)
◦ Defining the domain as the set of all students (in the world), and letting C(x)
denote the statement “student x is in the class (under consideration)”, we
say:  x (C(x) ∧ M(x)) , which means “there is a student (in the world) with
the properties: he is in the (concerned) class and has visited Mexico, or that
“being in the class and visiting Mexico” is true of one student (in the world).
◦ Note that we could not say:  x (C(x) ⇒ M (x)) as it would mean that “there
is a student (in the world) that, if in the class would have visited Mexico”, or
“being in the class implies visiting Mexico, is true of at least one student, but
not all” which is of course ridiculous, as it leads to a semantic collision
between what is has universal connotation (implication) and what is
existential (quantifier).
 Using a two-variable predicate Q(x,y) as before, and defining the domain as the
Predicate logic and English: Ex1 from sys specs
Every mail message larger than 1 MB will be compressed
 Letting L(x) be a predicate denoting that message x is larger than
1MB, and C(x) that message x will be compressed, then the above
statement expressed in predicate logic as one of:
◦ Defining the domain as the set of messages largeer than 1MB :  x C(x)
◦ Defining the domain as the set of all messages:  x (L(x) ⇒C(x))
 Using a two-variable predicate Q(x,y) to denote that message x is
larger than y MB, and C(x) that message x will be compressed,
then the above statement in predicate logic is:
◦ Def the domain as the set of all messages in the world: x(Q(x, 1) ⇒ C(x))
Predicate logic and English: Ex2 from sys specs
 Ex: Let A(x) represent the predicate “ user x is active, and
S(y, t) represent “(network) Link y is in state t, where one of
these states is “available”. Translate into predicate logic the
English statment
If a user is active, at least one link will be available
 We can see the implication between the premise “there is a
user active” and the conclusion “there is an available link”.
Thus, the above statement becomes in predicate logic as
follows:
 x A(x) ⇒  y S(y, available)
which can be read in reverse as: If there exists x such that A(x)
is true, then there exists y such that S(y, available) is true
 Recall that: There exists “some” … , means also there exists

“a” …, means also there exists “at least one” …

Comp231 Logic 231219

Uploaded by

Copyright:

Available Formats

Comp231 Logic 231219

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Comp231 Logic 231219

Uploaded by

Copyright:

Available Formats

 Sadat Academy

Instructor: Prof. Dr. Hamed Nassar

Dr. Hamed Nassar, Suez Canal Univ. 1

Dr. Hamed Nassar, Suez Canal Univ. 2

Prof. H. Nassar, BAU

Prof. H. Nassar, BAU

 New (compound) propositions can be produced from

 Logical operators: Just as there are arithmetic

Prof. H. Nassar, BAU

Truth Table of “NOT”

 Example: p=At least 10 inches of rain fell in Beirut yesterday

Prof. H. Nassar, BAU

Prof. H. Nassar, BAU

Prof. H. Nassar, BAU

Prof. H. Nassar, BAU

 Other forms of implication:

Prof. H. Nassar, BAU

 “if” in computer programs:

Prof. H. Nassar, BAU

 Truth Table of Converse, Contrapositive, and Inverse:

Prof. H. Nassar, BAU

Prof. H. Nassar, BAU

Prof. H. Nassar, BAU

 Note that a biconditional a iff b is equiv

Prof. H. Nassar, BAU

Prof. H. Nassar, BAU

 Precedence of Logical Operators:

Prof. H. Nassar, BAU

 Alternative: r = ride roller coaster r’ = does not ride

 s = automated reply is sent s’ = automated reply is NOT sent

 HW: P. 16 . . . : Solve 1, 4, 13, 20, 22, 33, 36, 45.

Prof. H. Nassar, BAU

 Alternative: s = diagnos msg stored in buffer, r = diagnos msg retransmistted

 Alternative: A says “B is a knight” (1), B says “we are opposites” (2)

Prof. H. Nassar, BAU

Prof. H. Nassar, BAU

 Tautology: is defined for ONE compound proposition (as it

Prof. H. Nassar, BAU

Prof. H. Nassar, BAU

Prof. H. Nassar, BAU

Prof. H. Nassar, BAU

Prof. H. Nassar, BAU

 HW: p. 28 . . . : 10, 17, 25, 33

Prof. H. Nassar, BAU

Prof. H. Nassar, BAU

Prof. H. Nassar, BAU

Prof. H. Nassar, BAU

Prof. H. Nassar, BAU

Prof. H. Nassar, BAU

Prof. H. Nassar, BAU

Prof. H. Nassar, BAU

Prof. H. Nassar, BAU

 I am going to compile a C-program I just wrote.

Prof. H. Nassar, BAU

 Statement: x is greater than 3

 P(x): P is a predicate and x is the subject, or P is a propositional

 Ex (Predicate Q, in two variables x,y):

Prof. H. Nassar, BAU

Prof. H. Nassar, BAU