Compound Propositions and Useful Rules

Type classification: this is a lesson resource.

Welcome! This is a lesson in the Introductory Discrete Mathematics for Computer Science course here at Wikiversity.

Compound Propositions

A compound proposition is a proposition that involves the assembly of multiple statements. This concept was also discussed a bit in the previous lesson.

Writing Truth Tables For Compound Propositions

To write the truth table for a compound proposition, it's best to calculate the statement's truth value after each individual operator. For example, in the statement $p\vee \neg q\to q$ , it's best to solve for $\neg q$ , then for $p\vee \neg q$ , and finally for the statement as a whole:

p	q	$\neg q$	$p\vee \neg q$	$p\vee \neg q\to q$
T	T	F	T	T
T	F	T	T	F
F	T	F	F	T
F	F	T	T	F

Showing Logical Equivalence

Logical equivalence means that the truth tables for two statements are the same. This was also discussed a bit in the previous lesson. In order to prove logical equivalence, simply draw the truth tables for all the statements in question and show that they are the same.

For example, you can show that $\neg p\vee q$ is logically equivalent to $p\to q$ .

p	q	$\neg p$	$\neg p\vee q$	$p\to q$
1	1	0	1	1
1	0	0	0	0
0	1	0	1	1
0	0	1	1	1

The Contrapositive, Inverse and Converse

The contrapositive of conditional statement $p\to q$ is $\neg q\to \neg p$ . A conditional is logically equivalent to its contrapositive. In other words, if q did not occur, then we can assume p also did not occur.

The inverse is $\neg p\to \neg q$ .

The converse is $q\to p$ .

The converse and inverse are logically equivalent. They are one another's contrapositives...

Tautology

A tautology is a statement that is always true. Another wording is that a tautology is a statement that is logically equivalent to the constant truth.

$p\to q\leftrightarrow \neg q\to \neg p$ is an example of a tautology.

Congratulations

Congratulations! You have finished the first lesson of the course.

Review this lesson

Return to main page