REVIEW
FOR SECTION 2
In this second section of the course you have moved from being able to
symbolize an expression and decide its truth value to being able to use
a truth-table method to decide (1) whether any two expressions are
logically equivalent (meaning only that they have the same truth value,
which disregards any consideration of when something is happening) and
(2) whether an intended argument form is valid (meaning that it is not
possible for the conclusion to be false whenever all the premises are
true).
For equivalences we will continue to examine complete truth tables in
order to see whether the main connectives in each expression correspond
exactly. For deciding validity, however, we are working with a
reverse method in which the task is to see whether what I am calling a
bad line (a line on the table in which the premises are all true but
the
conclusion is false.
1.
P -> (Q v R), S -> P, S & ~Q |- R
P Q
R S || P -> (Q v R) | S
-> P | S & ~Q | R
x
0 0
1
1
1
1 0
valid
2. P -> (Q v R), P ->
S, ~S |- ~(Q v R)
P Q
R S || P -> (Q v R) | P
-> S | ~S | ~(Q v R)
0
1 1
0
1
1 1 0
invalid
(other bad lines are
possible as well)
We also began with the use of proofs
or derivations. For this section we are limiting ourselves to
proofs for equivalence, which use a set of equivalence or replacement
rules that allow us to change the look of a complete expression (or
just a part of that expression) without in any way changing its truth
value.
The set of rules we now have:
Commutation (Com)
P & Q :: Q & P
P v Q :: Q v P
P<->Q :: Q<->P
Association
(Assoc)
P & (Q & R) :: (P & Q) &
R
P v (Q v R) :: (P v Q) v
R
(Do note that this relationship does not
apply to biconditionals.)
Distribution (Dist)
P & (Q v R) :: (P & Q) v (P & R)
P v (Q & R) :: (P v Q) & (P v R)
Double
Negation (DN)
P :: ~~P
In
the application of all other rules, in order to shorten the number of
steps
in a derivation, we allow DN to be understood rather than expressed
DeMorgan's
Law (DM)
~(P & Q) :: ~P v ~Q
~(P v Q) :: ~P & ~Q
Implication
(Impl)
P -> Q :: ~P v Q be careful to negate what is to the left
of the arrow
Equivalence (Equiv)
P <-> Q :: (P -> Q)
& (Q -> P)
Transposition
(Trans)
P -> Q :: ~Q -> ~P
Quantifier Negation (QN
~(x)Fx ::
(Ex)~Fx note that we never have an expression such
as ~x
In a derivation we number each step (our call lines) beginning with
the original expression and an indication of what we mean to show, then
we work step by step from that line to the expression we intend to show
has the same value. After each step, in what we call a justification, we indicate
the call line from which we take the expression (or part) of the
expression that we mean to transform, and we cite the specific rule
that allows this transformation.
For example, to show the equivalence of (P & Q) -> R and P -> (Q -> R) we
would do
the following:
1. (P & Q) ->
R / show P -> (Q ->
R)
1. P -> (Q -> R) / show (P
& Q) -> R
2. ~(P & Q) v
R 1,
Impl
2. ~P v (Q -> R) 1, Impl
3. (~P v ~Q) v
R 2,
DM
3. ~P v (~Q v R) 2, Impl
4. ~P v (~Q v
R) 3,
Assoc
4. (~P v ~Q) v R 3, Assoc
5. P -> (~Q v
R) 4,
Impl
5. ~(~P v ~Q) -> R 4. Impl
6. P -> (Q ->
R) 5,
Impl
6. (P & Q) -> R 5.
DM
(This relationship is often listed as a separate replacement rule
called exportation.)
Do we always need to do two
derivations? Actually, as long as only equivalence or
transformation rules are being used, going from just one expression to
the other is enough (and this will be all I expect on the review test
coming up).
For your second
review test, in addition to working with symbolization as you have
before,
you should be ready to do these two new things: (1) use a reverse
method test to determine the validity of an argument form that does not
involve quantifiers, (2) present derivations to show step by step
how to move from one expression to another that is logically equivalent
(has the same truth values for the main connective for each line of a
truth table).