Associated Topics || Dr. Math Home || Search Dr. Math

### Mathematical Logic

```
Date: 02/09/2001 at 21:48:25
From: ONG YEN CHIN
Subject: Logic

Given

~c <-> (a n b) and
d <-> [(a n ~b) u (b n ~a)]

where

~ = not
<-> = if and only if
n = and
u = or

how do I prove this?

(c n ~d)<->(~a n ~b)

I would appreciate your help very much. Thanks.

Kind regards,
Yen Chin
```

```
Date: 02/13/2001 at 20:05:13
From: Doctor Achilles
Subject: Re: Logic

Hi Yen Chin,

Thanks for writing Dr. Math. Mathematical logic is one of my
specialties, so I'll give your problem a try.

One thing I should say before I start: there is more than one set of
rules for derivations in mathematical logic, so I will show you how
to do your derivation using the rules I've learned.

These are the rules I've learned (they're pretty standard, so you can

A (assumption):
I will introduce assumptions with { and close them off with }.
Once a { has been closed by a }, anything between the squiggly
brackets is {off limits} for future steps. However, you can take
things down from above a { as long as it hasn't been closed off.

Note: Each operation (and, or, not, if-then, and if-and-only-if) has
an "introduction" rule and an "elimination" rule. The first states
that if you have proved certain facts about p and q, then you have
shown that the operation holds for p and q (or just p, in the case of
not). The second states that if you have proved the operation holds
for p and q, then you can derive certain other facts about p and q.

nI (n intro):
p on one line and q on another gives (p n q).

nE (n elim):
(p n q) on one line gives p (or q if you want it instead).

uI (u intro):
p on one line gives (p u q) where q is anything.

uE (u elim):
Start with (p u q). Assume p, derive r. Assume q, derive r. This
gives (p u q) -> r.

->I:
Assume p, derive q. This gives (p -> q).

->E:
(p -> q) on one line and p on another gives q.

<->I:
(p -> q) and (q -> p) gives (p <-> q).

<->E:
(p <-> q) and p gives q. (p <-> q) and q gives p.

~I:
Assume p, derive a contradiction (e.g. (q n ~q)). This gives ~p.

~E: ~~p gives p.

DeMorgan's rule:
~(p n q) <-> (~p u ~q) AND
~(p u q) <-> (~p n ~q)

Disjunctive syllogism (DS):
((p u q) n ~p) -> q

DeMorgan's rule and DS can be derived from the other rules, but they
are useful shotcuts.

One more note: the first two assumptions here are not going to be
closed off since we're trying to show that (c n ~d)<->(~a n ~b) is
true given those assumptions.

{
1)  ~c <-> (a n b)                      (A, given by the problem)
{
2)  d <-> [(a n ~b) u (b n ~a)]      (A, given by the problem)
{
3)  (c n ~d)                    (A, for ->I)
4)  c                           (nE on line 3)
{
5)  (a n b)                 (A, for ~I)
6)  ~c                      (<->E on lines 1 and 5)
7)  c                       (repetition of line 4)
8)  (c n ~c)                (nI on 6-7: contradiction)
}                             (close off A at line 5)
9)  ~(a n b)                    (~I on 5-8)
10) (~a u ~b)                    (DeMorgan's on 9)
11) ~d                           (nE on from line 3)
{
12) [(a n ~b) u (b n ~a)]    (A, for contradiciton)
13) d                        (<->E on lines 2 and 12)
14) ~d                       (repetition of line 11)
15) (d n ~d)                 (nI on 13-14: contradiction)
}                             (closes off A at line 12)
16) ~[(a n ~b) u (b n ~a)]       (~I on 12-15)
17) [~(a n ~b) n ~(b n ~a)]      (DeMorgan's on 16)
18) ~(a n ~b)                    (nE on 17)
19) ~(b n ~a)                    (nE on 17)
20) (~a u b)                     (DeM on 18)
21) (~b u a)                     (DeM on 19)
22) (~a u ~b)                    (Rep of 10)
{
23) a                        (A for ~I)
24) b                        (DS on 20)
25) ~b                       (DS on 22)
26) (b n ~b)                 (nI on 24-25: contradiction)
}                             (closes off A on 23)
27) ~a                           (~I on 23-26)
{
28) b                        (A for ~I)
29) a                        (DS on 21)
30) ~a                       (DS on 22)
31) (a n ~a)                 (nI on 29-30: contradiction)
}                             (closes off A on 28)
32) ~b                           (~I on 28-31)
33) ~a                           (Rep of 27)
34) (~a n ~b)                    (nI on 32-33)
}                                 (closes off A on 3)
35) (c n ~d) -> (~a n ~b)            (->I on 3-34)

Phew! We're halfway there (the next half is much shorter). Here's a
start for it:

{
36) (~a n ~b)                        (A for ->)
37) ~c <-> (a n b)                   (Rep of 1)
38) d <-> [(a n ~b) u (b n ~a)]      (Rep of 2)

From here you want to derive c and ~d. Try assuming ~c and getting a
Once you've done all that put c and ~d together and close off the
assumption at 36. That should give you (~a n ~b) -> (c n ~d). Then
you just have to put that together with line 35 using the rule <->I.

problems some more, please write back.

- Doctor Achilles, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
College Logic
High School Logic

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search