EF Logical analysis

Section 1.3 Logical analysis

We will now leave the English language behind and concentrate on logical statements consisting only of variables and connectives. Keep in mind that variables are not limited to representing simple statements; they can represent compound statements as well.

🔗

truth value: 🔗
the property of being true or false

🔗

Given a logical statement, view the variables as inputs and the truth value of the entire statement as an output. We would like a systematic way to determine how the truth value of the output changes as we vary the truth values of the inputs.

🔗

logical analysis: 🔗
the process of determining the truth value of a statement based on the truth values of its variable substatements
truth table: 🔗
tabular method of carrying out logical analysis

🔗

If a statement involves a finite number of variables, then since each variable can have one of only two possible truth values, there are a finite number of different combinations of input truth values for the statement. So we can test each combination one after the other to determine all possible outputs. Arrange this analysis in a table with all possibilities for the input variables on the left and the resulting outputs on the right.

🔗

Note 1.3.1.

🔗

In fact, if there are

n

variables, then there are exactly

2^{n}

different combinations of truth values for the variables.

🔗

First, let’s establish the truth tables of the basic connectives (that is, of statements containing exactly one connective).

Negation

$p$	$\neg p$
$T$	$F$
$F$	$T$

Conjunction

$p$	$q$	$p \land q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$F$
$F$	$F$	$F$

Disjunction

$p$	$q$	$p \lor q$
$T$	$T$	$T$
$T$	$F$	$T$
$F$	$T$	$T$
$F$	$F$	$F$

Conditional

$p$	$q$	$p \to q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$T$
$F$	$F$	$T$

Biconditional

$p$	$q$	$p \leftrightarrow q$
$T$	$T$	$T$
$T$	$F$	$F$
$F$	$T$	$F$
$F$	$F$	$T$

🔗

Figure 1.3.2. The truth tables of the Five basic connectives.

🔗

Note 1.3.3.

🔗

🔗
Conjunction $p \land q$ is true only when both $p$ and $q$ are true.
🔗
Disjunction $p \lor q$ is true when at least one of $p$ and $q$ is true.

See.

🔗
Statement 2 of Remark 1.1.5 for the difference between inclusive or and exclusive or.
🔗
The first two rows of the truth table for $p \to q$ are consistent with the reading “if $p$ is true then $q$ is also true.” Really, this reading of the conditional says nothing in the case that $p$ is actually false, but we cannot leave the “output” column of the truth table blank for the corresponding rows where $p = F .$ Instead, the outputs in the last two rows of the truth table for $p \to q$ are “default” values chosen to avoid inconsistencies. (See Exercise 1.6.3.)
🔗
Looking at all four rows of the truth table for $p \to q,$ we can succinctly say that $p \to q$ is true except when $p$ is true but $q$ is false.
🔗
Biconditional $p \leftrightarrow q$ reads “ $p$ is true when $q$ is true, and only when $q$ is true.” But this means that when $q$ is false, $p$ cannot be true, hence must by false, which explains the fourth row of the truth table.
🔗
Looking at all four rows of the truth table for $p \leftrightarrow q,$ we can succinctly say that $p \leftrightarrow q$ is true when $p$ and $q$ have the same truth value.

🔗

We can now use the truth tables of the basic connectives to analyze more complicated statements. Liberal use of extra “intermediate” columns to analyze substatements separately is highly recommended.

🔗

Worked Example 1.3.4.

🔗

Analyze

\neg (p \leftrightarrow q) .

Solution.

$p$	$q$	$p \leftrightarrow q$	$\neg (p \leftrightarrow q)$
$T$	$T$	$T$	$F$
$T$	$F$	$F$	$T$
$F$	$T$	$F$	$T$
$F$	$F$	$T$	$F$

🔗

Note 1.3.5.

🔗

The logical statement

\neg (p \leftrightarrow q)

analyzed in Worked Example 1.3.4 is one way to realize exclusive or:

p

q

but not both.

🔗

Worked Example 1.3.6.

🔗

Analyze

(p \land q) \to (p \leftrightarrow r) .

Solution.

$p$	$q$	$r$	$p \land q$	$p \leftrightarrow r$	$(p \land q) \to (p \leftrightarrow r)$
$T$	$T$	$T$	$T$	$T$	$T$
$T$	$T$	$F$	$T$	$F$	$F$
$T$	$F$	$T$	$F$	$T$	$T$
$T$	$F$	$F$	$F$	$F$	$T$
$F$	$T$	$T$	$F$	$F$	$T$
$F$	$T$	$F$	$F$	$T$	$T$
$F$	$F$	$T$	$F$	$F$	$T$
$F$	$F$	$F$	$F$	$T$	$T$

🔗

Worked Example 1.3.7.

🔗

Analyze

((p \to q) \to r) \leftrightarrow (p \to (q \to r)) .

Solution.

$p$	$q$	$r$	$p \to q$	$q \to r$	$A$	$B$	$A \leftrightarrow B$
$T$	$T$	$T$	$T$	$T$	$T$	$T$	$T$
$T$	$T$	$F$	$T$	$F$	$F$	$F$	$T$
$T$	$F$	$T$	$F$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$F$	$T$	$T$	$T$	$T$
$F$	$T$	$T$	$T$	$T$	$T$	$T$	$T$
$F$	$T$	$F$	$T$	$F$	$F$	$T$	$F$
$F$	$F$	$T$	$T$	$T$	$T$	$T$	$T$
$F$	$F$	$F$	$T$	$T$	$F$	$T$	$F$

Elementary Foundations: An introduction to topics in discrete mathematics

Search Results:

Section 1.3 Logical analysis

Note 1.3.1.

Note 1.3.3.

Worked Example 1.3.4.

Note 1.3.5.

Worked Example 1.3.6.

Worked Example 1.3.7.