Examples of logically equivalent statements - College of Arts ...

Propositional Logic

Grinshpan

Examples of logically equivalent statements

Here are some pairs of logical equivalences. Each may be verified via a truth table.

p¡Äq

q¡Äp

commutativity of ¡Ä

p¡Åq

q¡Åp

commutativity of ¡Å

?(?p)

p

double negation

(p ¡Ä q) ¡Ä r

p ¡Ä (q ¡Ä r)

associativity of ¡Ä

(p ¡Å q) ¡Å r

p ¡Å (q ¡Å r)

associativity of ¡Å

p ¡Ä (q ¡Å r)

(p ¡Ä q) ¡Å (p ¡Ä r)

distributivity of ¡Ä over ¡Å

p ¡Å (q ¡Ä r)

(p ¡Å q) ¡Ä (p ¡Å r)

distributivity of ¡Å over ¡Ä

?(p ¡Ä q)

?p ¡Å ?q

de Morgan¡ä s law

?(p ¡Å q)

?p ¡Ä ?q

de Morgan¡ä s law

p ¡Å (p ¡Ä q)

p

absorption law

p ¡Ä (p ¡Å q)

p

absorption law

p¡Äp

p

idempotency

p¡Åp

p

idempotency

p¡úq

?p ¡Å q

p¡úq

?q ¡ú ?q

p?q

(p ¡ú q) ¡Ä (q ¡ú p)

Note that two statements P and Q are equivalent whenever P ? Q is a tautology.

In the table below, T represents a statement that is always true and F represents a

statement that is always false.

p¡ÄT

p

p¡ÅT

T

p¡ÄF

F

p¡ÅF

p

p ¡Ä ?p

F

p ¡Å ?p

T

Precedence of logical operations

?

1

¡Ä

2

¡Å

3

¡ú

4

?

5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download