CS 100 - Week 14 Lecture 2 - 11-29-12
Chapter 10 - a little propositional logic
...but, really, this is a CONTINUATION
of what we did with truth tables back in
week 2 and 3!
* in propositional logic, our Boolean and
operation is called CONJUNCTION,
and it is often written as &
* in propositional logic, our Boolean or
operation is called DISJUNCTION,
and it is often written as v
* in propositional logic, our Boolean not
operaton is called NEGATION,
and it is often written as ~
* and in a propositional logic truth
table, one often uses T and F for true
and false
...so, here are three truth tables using this
propositional knowledge notation (or syntax,
if you will!):
conjunction:
p q p&q
---------
T T T
T F F
F T F
F F F
disjunction:
p q pvq
---------
T T T
T F T
F T T
F F F
negation:
p ~p
-----
T F
F T
* conditional statements have a truth-table
form, too!
if A, then B.
in propositional logic, you represent this
as: A->B
if p, then q
... p->q
* here's the thing about a conditional
statement -- it is considered to be
true as long as, IF the antecedent (the
if part) is true, THEN the consequent
(the then part) is true;
p q p->q
-----------
T T T
T F F
F T T
F F T
* you can indicate that some "operation" is
being done on a compound statement by
putting that compound statement in
parentheses as needed --
~p&q -> means "not p" AND q
~(p&q) -> means not "p and q"
..negate the conjunction!
* SIMPLE example: using truth tables to
determine argument validity for some
kinds of deductive arguments...
Tina is tall.
Sarah is tall.
So, Tina is tall, and Sarah is tall.
* for convenience, assign a variable to each statement;
p="Tina is tall"
q="Sarah is tall"
* ...then I can write this argument
in propositional logic form as:
p
q
.'. p&q
...where the .'., intended to be a triangle made up of
3 dots, means "thus" or "therefore" or "so", indicating
that this is the conclusion, this is what follows from
the premises on the preceding lines
* make a truth table for this:
p q p&q
------------
T T T
T F F
F T F
F F F
* mark the headings that are premises with a *, and the heading
of the conclusion with a C
p* q* p&qC
------------
T T T
T F F
F T F
F F F
* CIRCLE the premises and conclusion ONLY in rows where ALL
the premises are true --
...I'm simulating circling with ( ) here. Please pretend they
are circles.
p* q* p&qC
------------
(T) (T) (T)
T F F
F T F
F F F
* how do you tell if this argument is valid?
IF, for EVERY row of the truth table where ALL the premises are
true, the conclusion is ALSO true, then it is indeed the
case that the premises being true guarantees that the
conclusion is true --
...that's the definition of a valid deductive argument, and
thus demonstrates that the argument is deductive.
* do you see that this is true here? Only 1 row has both
premises true, and the conclusion is indeed true in that
row, so this argument IS valid.
* SO -- SUMMARIZING how can you use a truth table to determine the validity
of some deductive arguments expressed in propositional logic form:
* FIRST, assign a variable to each statement involved
* [note: you aren't limited to p and q, and sometimes you
will have more than 2 letters -- you are allowed to use
other letters, although v is problematic and should be
avoided (because of how disjunction
is written in propositional logic as a v)]
* SECOND, write the argument in propositional logic form
* THIRD, make the truth table for the premises and conclusion
involved
* note: it is EXPECTED that the first columns are the single
variables, and then the subsequent columns are operations
on those variables, building from simplest to most complex;
* note: with 2 variables, the first is EXPECTED to have its
possible values written in the order T, T, F, F, and the
second is EXPECTED to have its possible values written in the
order T, F, T, F (and then the operations are filled in
based on the values of these two varaibles);
...with 3 variables, the first is EXPECTED to have its
possible values written as T, T, T, T, F, F, F, F,
the second is EXPECTED to have its possible values written in
the order T, T, F, T, T, T, F, F, and the third is
EXPECTED to have its possible values written in the order
T, F, T, F, T, F, T, F
...and so on;
* FOURTH, mark each premise with a *
after its expression in the heading of
the truth table,
AND mark the conclusion in the heading
of the truth table with a C
* [optionally, you can repeat columns so that the
conclusion is the last column; you can also repeat
premise columns so they are "nearer" to the conclusion,
if you would like]
* FIFTH, indicate those rows/values where
ALL the premises are true --
I circled the premise value(s) and the
conclusion value(s) on JUST such rows
FINALLY -- look at those rows with circled values.
...if, for ALL such rows, the conclusion
is TRUE, then the argument is valid;
if, for even a SINGLE such row,
the conclusion is FALSE, then the
argument is deductively NOT valid,
INvalid --
all its premises being true DOESN'T
guarantee that its conclusion is true.
* a NOT valid example:
Grass is green.
So, grass is green, and the sky is blue.
* assign a variable to each statement involved:
p=Grass is green.
q=The sky is blue.
* write this argument in propositional logic form:
p
.'. p&q
* make the truth table for the premises and conclusion involved
p q p&q
-------------
T T T
T F F
F T F
F F F
* mark the heading(s) that are premises with a *, and the heading
for the conclusion with a C:
p* q p&qC
-------------
T T T
T F F
F T F
F F F
* CIRCLE the premises and conclusion ONLY in rows where ALL
the premises are true --
only 1 premise here, so circle for all where IT is true:
p* q p&qC
-------------
(T) T (T)
(T) F (F)
F T F
F F F
* NOW -- is it true that, for every row where the single premise
is true (that's "all" the premises here!), that the conclusion
is ALSO true?
NO -- 2nd row has true premise, and FALSE conclusion;
SO -- the premise being true doesn't GUARANTEE that the conclusion
is true, so this argument is NOT valid.
* an example to demo that the conclusion
doesn't HAVE to be the rightmost column
(and it is OK to repeat columns so that
it is, for your sanity)
Franklin is short and stout.
So, Franklin is short.
let:
p=Franklin is short
q=Franklin is stout
then, this argument can be written in
propositional logic form as:
p&q
.'. p
p q p&q
-------------
T T T
T F F
F T F
F F F
* marking the premise and conclusion:
pC q p&q*
-------------
T T T
T F F
F T F
F F F
* ...and choosing to repeat the conclusio row on the right,
so more obvious/readable
pC q p&q* pC
-----------------
T T T T
T F F T
F T F F
F F F F
* circling the premise and conclusion only for each row
where the premise is true:
pC q p&q* pC
-----------------
T T (T) (T)
T F F T
F T F F
F F F F
* and in the only row where the premise is true, the
conclusion IS true,
...and so, we've shown this argument
IS deductively valid
* let's throw in an example with negation
* FIRST: just a truth table for a statement
involving conjunction and negation:
Tina is tall, and Sarah is not tall.
let:
p=Tina is tall
q=Sarah is tall
~q=Sarah is not tall
p q ~q p&~q
--------------
T T F F
T F T T
F T F F
F F T F
* now for an ARGUMENT using something like
this:
Tina is not tall, and Sarah is tall.
So, Tina is not tall.
let:
p=Tina is tall
q=Sarah is tall
~p=Tina is not tall
this argument would be written in
propositional logic form as:
~p&q
.'. ~p
p q ~pC ~p&q*
--------------
T T F F
T F F F
F T T T
F F T F
* repeating the conclusion row on the right (if you'd like)
p q ~pC ~p&q* ~pC
--------------------
T T F F F
T F F F F
F T T T T
F F T F T
* circle premise(s) and conclusion ONLY in rows where ALL
the premise(s) are true
p q ~pC ~p&q* ~pC
--------------------
T T F F F
T F F F F
F T T (T) (T)
F F T F T
* since, in the only row where the premise is true,
the conclusion is true, this argument IS valid;