1.2: More on Logical Statements

Properties

The following are some of the most frequently used logical equivalencies when writing mathematical proofs.

Theorem \(\PageIndex{1}\)

Let \(p\) and \(q\) be statements. Then the following statements are true:

1. \(p \vee p \equiv p\), and \(p \wedge p \equiv p. \)
2. \(p \vee q \equiv q \vee p\) and \(p \wedge q \equiv q\wedge p\).
3. \(\neg(p \vee q)\equiv \neg p \wedge \neg q \) and \(\neg(q \vee p) \equiv \neg q \wedge \neg p \).
4. \(p \rightarrow q \equiv \neg q \rightarrow \neg p\).
5. \(p \rightarrow q \equiv \neg p \vee q\).
6. \(\neg (\neg p) \equiv p\).
7. \(p \leftrightarrow q \equiv (p \rightarrow q) \wedge ( q \rightarrow p)\).

Predicate Logic

If we add the words “every”, “there is”, “all” and “some” to the list of logic terms we would get what is known as the predicate logical system.

The two quantifiers are:

1. For all (every) \(x\), \(P(x)\), is denoted by \(\forall x P(x) .\)
2. There exists (at least one) \(x\) such that \(P(x)\), is denoted by \( \exists x P(x).\)

Example \(\PageIndex{1}\):

1. Every student in this class has studied high school mathematics. By using notation, we can write, \( \forall x \,P(x) \), where \(P(x)\):= \(x\) has studied high school mathematics.
2. For every integer \(x\), there exist an integer \(y\) such that \(x+y=x\). By using notation, we can write, \( \forall \, integer\, x, \exists \, integer\, y\) such that \(x+y=x\).

Example \(\PageIndex{2}\):

Consider the form “X dislikes Y”.

If both variables are universally quantified, it translates as “For all X, for all Y, X dislikes Y.” In English, "Everyone dislikes everyone."

If the first variable is universally quantified and the second is existentially quantified it translates as, “For all X, there is a Y (such that) X dislikes Y”. In English, “Everyone dislikes someone".

Example \(\PageIndex{3}\):

For every X, there is a Y such that Y is X’s mother.

For every Y, there is an X such that Y is X’s mother.

The first statement says “Everyone has a mother”, while the second says “Everyone is a mother".

Negating statement with Quantifiers:

1. Let p be the statement \(\forall x P(x) .\) Then \(\neg\, p\) is \( \exists x, \neg\,P(x).\)
2. Let q be the statement \(\exists x P(x) .\) Then \(\neg\, q\) is \( \forall x, \neg \, P(x).\)

Example \(\PageIndex{4}\):

1. Every student in this class has studied high school mathematics. By using notation, we can write, \( \forall x \,P(x) \), where \(P(x)\):= \(x\) has studied high school mathematics.

Negation: There is a student in this class has not studied high school mathematics.

2. For every integer \(x\), there exist an integer \(y\) such that \(x+y=x\). By using notation, we can write, \( \forall \, integer \,x, \exists \, integer\, y\) such that \(x+y=x\).

Negation: For every integer \(y\), there exist an integer \(x\) such that \(x+y\ne x\).

Compound statements with quantifiers

Example \(\PageIndex{5}\):

Let \(Q\) be the statement: For all real numbers \(a\) and \(b,\) if \(a+b\) is irrational or \(a-b\) is irrational then \(a\) is irrational and \(b\) is irrational.

1. Write the contrapositive of Q.

Answer

For all real numbers \(a\) and \(b,\) if \(a\) is rational or \(b\) is rational then \(a+b\) is rational and \(a-b\) is rational.

​​​​​

2. Write the converse of Q.

Answer

For all real numbers \(a\) and \(b,\) if \(a\) is irrational and \(b\) is irrational then \(a+b\) is irrational or \(a-b\) is irrational.

3. Write the negation of Q.

Answer

There exist real numbers \(a\) and \(b,\) such that \(a+b\) is irrational or \(a-b\) is irrational, but \(a\) is rational or \(b\) irrational.

​​​​​​

Terminology: Theorem, Q.E.D, and Conjecture

Theorems and Conjectures

• A theorem is a mathematical statement that has been proved using, and built upon, other statements, theorems, and standard axioms.
• A conjecture is a mathematical statement that is thought to be true but has not yet been proven formally in the field.

Thinking out loud

Can you think of a theorem and a conjecture?