Textbook Notes
(363,221)

United States
(204,443)

Temple University
(1,805)

CIS 1166
(4)

David Shulman
(4)

Chapter

# PropLogic.pdf

Unlock Document

Temple University

Computer & Information Science

CIS 1166

David Shulman

Spring

Description

Propositional Logic
This note contains some material on propositional logic. It is not intended
to be a substitute for your textbook or the class lectures. It is instead a
supplement and to some extent a guide to what is important.
1 Propositions
A proposition is something that has a de▯nite truth value, true or false.
Thus commands or questions or exclamations are not propositions. Nor is
something like x + 1 = 5 a proposition if we do not know the value of x.
What x + 1 = 5 is is a propositional formula; if we specify the value of
certain variables, then a propositional formula becomes a proposition.
A proposition, for our purposes is not vague or ambiguous. So something
like "I went to the bank" is not a proposition unless it is known which
meaning of bank (▯nancial institution or riverbank) is intenced.
Just as in algebra we use symbols like x, y, z to refer to unknown quanti-
ties, in propositional logic we can use symbols like p, q, r to refer to propo-
sition whose truth values we might not know.
1.1 Propositional Operators
There are several important operators (also called connectives) that take one
or more propositions as input and output a proposition. These connectives
are truth-functional in the sense that if we know the truth values of the
inputs, then we know the truth values of the output.
1.1.1 Negation
The symbol : is used to represent negation.
:P is true if P is false and :P is false if P is true.
If you are building a circuit and want to represent your combinatorial
circuit (combinatorial in the sense that you only care about which input
signals reach your gates rather than the timing of when they reach the logic
gates), there is a standard symbol for an invertor which implements negation
(see section 1.2).
1 The proposition :P has the English language translation: It is not the
case that P. The resulting translation might be very unsmooth, unnatural
and unidiomatic. So you might want to use a clearer and more colloquial
translation if P is complicated.
Instead of
It is not the case that George was late for his appointment
George was not late for his appointment.
Instead of
It is not the case that Laura ate at least three frankfurters
Laura did not eat at least three frankfurters
or
Laura ate fewer than three frankfurters.
Instead of
It is not the case that George was not early for his appointment
George was early for his appointment.
This last translation uses the rule that ::P has the same truth value as
P.
1.1.2 Conjunction
The symbol ^ is used to represent conjunction.
P ^ Q is true if both P and Q are true.
P ^ Q is false if P is false.
P ^ Q is false if Q is false.
(In section 1.1 of your textbook, you will see a truth table for this con-
nective.)
The simplest translation of P ^ Q is P and Q. But natural language is
tricky. In formal logic I can say P ^ Q without there being any suggestion
that P and Q have anything to do with each other; all I am doing is asserting
that they are both true. Moreover, in English if there is a contrast between
P and Q, then the word "but" rather than "and" might be used as in
I do not like most hot, humid, cities but I like New Orleans.
In designing circuits, there is a special simple for a logic gate that im-
plements the and operation. In general, this gate might allow for more than
two inputs (but just one output). The rule is that the output is output rep-
resenting true whenever all the inputs represent true but if any input signal
represents false the output is false.
Your textbook displays a truth table for the and operator.
2 1.1.3 Disjunction
The symbol _ is used to represent disjunction.
P _ Q is false if both P and Q are false.
P _ Q is true if P is true.
P _ Q is true if Q is true.
Notice the similarity with the rules for ^. Start with the rules for ^ and
then convert ^ to _, and change true to false and false to true and you get
the rules for _.
We have the De Morgan Rules
:(P ^ Q) has the same true value as :P _ :Q because the only way
:(P ^Q) can be true is if P ^Q is false and that only happens if either P or
Q is false (or both are false) and that means that not P or not Q (or both)
is true and clearly if not P is true, then P ^ Q is false so :(P ^ Q) is true
and a similar statement can be made about Q.
(Note the proof technique I am using here to show that A and B always
have the same truth value, it is enough to show that whenever A is true, then
B is true and whenever B is true, A is true. So I start with the assumption
A is true and ask myself what could possibly make A true and then see if
I am forced to conclude that B is true and then I do the same thing in the
reverse direction.)
I have just stated only one of the De Morgan rules but the other De
Morgan rule is
:(P _ Q) has the same true value as :P ^ :Q.
Because of the De Morgan rules we can always rewrite
P _Q as :(:P ^:Q) (you might use a truth table or some other method
to prove this) and
we can always rewrite
P ^ Q as :(:P _ :Q).
Thus we do not really need both conjunction and disjunction operators
but it is convenient to be able to use both.
The usual translation of P _ Q is P or Q; however one should be careful.
In English the word "or" is ambiguous. It might be exclusive or (P or Q
but not both; in this situation one might say Either P or Q with an emphasis
on either) or inclusive or (P or Q or BOTH). _ is used for inclusive or.
For exclusive or, we have P ▯ Q, which is true i▯ exactly one of the
propositions P and Q is true.
3 There is a symbol that is used to represent an or gate. This or gate can
have two or more inputs and will have one output. The output signal will
represent true i▯ at least one of the input signals represents true.
1.1.4 Conditionals
P ! Q is true if P is true and Q is true.
P ! Q is true if P is false regardless of the value of Q.
P ! Q is false if P is true and Q is false.
P ! Q is translated as
if P then Q.
or as
P implies Q.
Here we refer to the P part of P ! Q as the antecedent and the Q part
as the consequent.
But this translation is perhaps a bit misleading. Natural language is
subtle.
First point to keep in mind is that a sentence like
If 2 + 2 = 5, then snow is white
is true because an implication is true whenever the antecedent is false.
So
If I am the Emperor of Antarctica, then mammoths inhabit the ▯rst
oor
of the White Hourse
is also a true proposition.
This might seem like a strange kind of if-then. But keep in mind that the
truth value of P ! Q depends only on the truth values of P and Q; there is
no implicature that P and Q have anything to do with each other.
So we also have
If I live in the United States of America, then water is H20
is a true proposition.
Aside from the relevancy issue, if you are still wondering why P ! Q is
true whenever P is false. consider that one application of prop[ositional logic
is system speci▯cation. We might specify a rule that whenever P is true, Q
must be true. If it turns out that P is false, then it does not matter what Q
is; we have not violated the rule. The rule is still true.
But conditionals really are a little trickier to translate than other con-
nectives. In English I might say if-then and mean much more than just
if-then:
4 If you give me ten dollars, I will give you the widget
might be said by a salesperson who also intends to mean that if you do
not give the ten dollars, you do not get the widget.
Consider now a situation in which to obtain a certain job, you have to
pass a certain exam. Then I might say that a necessary condition for you to
obtain the job is that you pass the exam or that it is necessary for you to
pass the exam in order to obtain the job. Or I could say that you will obtain
the job only if you pass the exam. If you do obtain the job, then you have
passed the exam.
But I have not said that all you have to do to obtain the job is pass the
exam. There might be other things you have to do. So that you pass the
exam is NOT su▯cient for you to obtain the job. However, we know that
if you obtained the job, you must have passed the exam. So in order for us
to KNOW that you passed the exam, it su▯ces that we know you obtained
the job. It is also clearly true that a su▯cient condition for you not to have
obtained the job is that you did not pass the exam.
If you think about examples like the job example, you should be able to
make sense of the various translations of ! given on the bottom of page 6
of your textbook.
Strictly speaking we do not need !, P ! Q and :P _ Q, which is
interpreted as (:P) _ Q, have the same truth value. But ! is convenient.
Numerous system requirements are very naturally expressed using if-then
statements.
1.1.5 Biconditionals
P $ Q is true if and only if P and Q have the same truth value (either both
true or both false).
Thus P $ Q has the same truth value as (P ! Q) ^ (Q ! P).
P $ Q might be translated as
If and only if P, then Q.
A necessary and su▯cient condition for Q is P.
P is necessary and su▯cient for Q.
(and besides these three, many other translations are possible).
5 1.2 Complex Operators
We can form more complex operations by taking two or more simple operators
and letting outputs of some of the operators be inputs to other operators.
What we have to be careful about (And do be careful; some students in
previous classes were not careful and wrote things that taken literally were
very wrong) is order of operations.
If you think of : as being like the minus sign, ^ as being like multipli-
cation, _ as being like addition, and ! as being like ▯ (because if P ! Q,
then Q is at least as true as P), then you will see why the precence order
is ▯rst do the negations, then the conjuncts, then the disjuncts, and then
conditionals. And it turns out biconditionals are last. Of course, you have
to pay attention to parentheses. You do what is within a parenthesis before
you do any operation that mixes up input from within the parenthesis and
from outside of the parenthesis.
Thus :p _ q ^ r ! p $ s is really
(((:p) _ (q ^ r)) ! p) $ s where we ▯rst do the negation, then we
compute q ^ r and then we do the _ and ▯nally we do the ! and the $.
We sometimes will add super
uous parentheses in order to make the order
of operations clear.
You should at least be clear about the relative precedence of not, and,
or, if-then.
1.3 A family of operations
There are several related operations we can perform given two inputs P and
Q.
We start with the conditional P ! Q.
then we take the converse Q ! P,
then we take the inverse :P ! :Q and
then we take the contrapositive :Q ! :P.
The inverse is probably not as important to knwo as the converse and
contrapositive.
People will often say thing like: If P then Q and conversely
in order to say that the implication works in both directions: If P then
Q but also if Q, then P.
People will often also say things like: If P then Q, but not conversely.
That means if P then Q si true but if Q then P is not a true statement.
6 The contrapostive is important because the original implication and the
contrapositive have the same truth value. If you know that it is true that if
P then Q, it might be convenient to reason from the fact that you know Q to
be false and hence not Q to be true|to reason from there to the conclusion
that P cannot be true if the implication is to be true.
So if we know that if you got the job, you passed the exam; we also know
that if you did not pass the exam, you did not get the job.
2 Evaluating Propositional Formulae
Given a complicated propositional formula containing many variables, we
might want to ▯gure out when the formula is true, for what values of the
inputs is the formula true. For this purpose we can use truth tables. This is
illustrated in the textbook and was discussed in class.
When you use truth tables you do have to be careful that you have covered
all possible combinations of truth values for the input variables. In general
if there are n inputs, there should be 2 rows in your truth table. Be careful
that you have covered all possible cases.
If a formula is true for all possible values of the inputs (all rows of the
truth table result in output true), we say the formuila is a tautology. But if
a formuia is false for all possible values of the inputs (all rows of the truth
table result in false output), then the formula is a contradiction. The third
alternative is a contingency. With a contingency, sometimes you obtain true
and sometimes you get false.
In addition to just working with one propositional formuia, we might
be working with two formulae and we might be curious if the two formulae
always have the same truth value. If they do, we say that they are equivalent.
We can use a truth table (be sure you have checked all cases) to recognize
whether two statements are equivalent.
We write p ▯ q to mean that p is equivalent to q. We have many rules
telling us which statements are equivalent to which other statements.
We can program a computer to automatically recognize whether a formula
is a tautology, a contradiction, or neither or to automatically recognize if two
formulae are equivalent. The computer (or you) could use truth tables. B

More
Less
Related notes for CIS 1166