3 - Logic

Statements

A statement is a declarative sentence that has a truth value (or claim)

$P,Q,$ and $R$ are commonly used to represent statements, though any symbol will do.

Assign letters to a symbols using a : not a =

For example:

P: 2 is an even number

Sentences involving unknown variables, such as $x$, are not considered statements.

Complex Statements

P ∧ Q is like P and Q in Python or P && Q in Javascript.

P V Q is like P || Q in Javascript or P or Q in Python. It is read P and Q.

You can say "not P". Similar to ! in JS or not in Python. Used with a whole statement you can say "it is not the case that" + $P$

Implications & Conditional Statements

If P is false (and Q is false or true), then the statement is true.

If P is true AND Q is true, the statement is true.

If P is true AND Q is false, the statement is false.

Biconditional Statements

If P And Q are both true or are both false, the statement is true. Otherwise, it is false.

P ⇔Q is the same as saying that P ⇒Q and Q ⇒ P.

A logical connective is an operation that modifies or combines statements into more complex statements. Examples of logical connectives are ∧, ∨, ¬, ⇒, and ⇔.

A compound statement is a statement that has been built by applying at least one logical connective to one or more statements. For example, ((P ∨Q)∧(R∨¬(S)))⇒(P ∧R).

Logical Equivalence

Two compound statements are logically equivalent if they have the same truth value. If R and S are compound statements that are logically equivalent, we write R ≡ S.

Each of the logical equivalences in Theorem 3.26 can be proved by constructing a truth table.

In other words, if two columns have different values, they are NOT logically equivalent.

Tautologies and Contradictions

Contradiction

A compound statement that is false for every possible combination of truth values of its components is called a contradiction.

For example $P\wedge (\neg P)$

Tautology

A compound statement that is true for every possible combination of truth values of its components is called a tautology.

For example $P\Rightarrow P$

Example of a compound statement that is a tautology: $(P\wedge (P\Rightarrow Q))\Rightarrow Q$.

All contradictions are logically equivalent to each other. Similarly, all tautologies are logically equivalent to each other.

Exercises - HW3

E 3.1
a) It is a statement. It's true.
b) It is not a statement.
c) It is not a statement.
d) It is a statement. It's false.
e) It is a statement. It's false.
f) It is a statement. It seems to be false.

E3.2
a)

b)

c)

d)

e)

E 3.3
a)

Since the columns containing $(\neg P)\vee (\neg Q)$ and $\neg (P\wedge Q)$ are equivalent, the two expressions are logically equivalent. The statement $\neg (P\wedge Q)\equiv (\neg P)\vee (\neg Q)$ is true.

b)

Since the columns containing $P\Rightarrow Q$ and $(\neg P)\vee Q$ are equivalent, the two expressions are logically equivalent. The statement $P\Rightarrow Q\equiv (\neg P)\vee Q$ is true.

c)

Since the columns containing $(P\vee Q)\Rightarrow R$ and $(P\Rightarrow R)\wedge (Q\Rightarrow R)$ are equivalent, the two expressions are logically equivalent. The statement $(P\vee Q)\Rightarrow R\equiv (P\Rightarrow R)\wedge (Q\Rightarrow R)$ is true.

E 3.4
a)

Since the truth values for any values $P$ and $Q$ are the same for P ∧ (¬Q) and ¬(P ⇒ Q), the two expressions are logically equivalent.

b)

Since the truth values for any values $P$ and $Q$ are the same for P ⇒ (¬Q ∨ R) and (P ∧ Q) ⇒ R, the two expressions are logically equivalent.

c)

Since the truth values for any values $P$ and $Q$ are the same for (P ∧ ¬Q) ⇒ R and P ⇒ (Q ∨ R), the two expressions are logically equivalent.

d)

The two expressions are NOT logically equivalent because some values of P and Q result in different truth values for the expressions. For example, when P is false and Q is true, $(P\vee Q)\Rightarrow R$ is false while $(\neg R\wedge P)\Rightarrow (\neg Q)$ is true.

e)

Since the truth values for any values $P$ and $Q$ are the same for P ⇔ Q and (P ⇒Q)∧(Q⇒P), the two expressions are logically equivalent.

E 3.5

a)

The statement $((P\Rightarrow Q)\wedge (\neg Q))\Rightarrow (\neg P)$ is a tautology since every possible combination of P & Q results in true.

b)

The statement $((P\vee Q)\wedge (\neg P))\Rightarrow Q$ is a tautology since every possible combination of P & Q results in true.

c)

This statement is neither a tautology nor a contradiction since not all values result in true or false.

d)

The expression ((¬Q) ⇒ (¬P)) ∧ P ∧ (¬Q) is false for all combinations of P and Q; therefore, it is a contradiction.

E 3.6

a)

Since the two tables right columns are not identical, the statements are not logically equivalent.

b)

Statement P: "It is raining." Statement Q: "The ground is wet."

P ⇒ Q: "If it is raining, then the ground is wet." This is (typically) true because rain typically makes the ground wet.

Q ⇒ P: "If the ground is wet, then it is raining." This is not necessarily true because there could be other reasons for the ground to be wet, such as BYU's awful sprinklers, a spilled drink, etc.

Truth value of P ⇒ Q: True
Truth value of Q ⇒ P: False