Logic Primer

Propositional Logic or Zero-Order Logic

authored by Premmi and Beguène

This is a work in progress.

Introduction

Cryptography involves the design of systems called cryptosystems that possess one or more security properties. For example, a cryptosystem might be designed to enable entities to communicate in such a way that, even if an eavesdropper intercepts their communication, no information can be gleaned from it. Alternatively, another cryptosystem may be designed to ensure the integrity of the transmitted message.

To argue that a cryptosystem is secure, we formulate the security properties that such a system should possess in terms of mathematical theorems, which are true statements. By proving that these theorems hold under plausible assumptions, we demonstrate the security of the system with respect to these properties.

A proof of a theorem is a justification of the theorem’s truth. It is constructed by drawing conclusions from statements initially accepted as true (called axioms) and from statements that have been previously proved. These conclusions are drawn using deductive reasoning, which involves the use of logic.

In this primer, we will discuss in detail how to write a proof of a theorem i.e., how to put together a sequence of statements that provides an acceptable justification for a theorem.

First, we will discuss the basic logic underlying proofs and then proceed to the essential methods involved in constructing correct proofs.

Proposition and Logical Connectives

As previously discussed, the proof of a theorem is based on drawing logical conclusions from statements that are either accepted as true or have been previously proved. Therefore, every statement involved in the construction of a proof must have a truth value of true. We call such statements that have exactly one truth value namely, true or false, as propositions.

For example, sentences like “ $7 > 3"$ and “There are eleven planets in our Solar System.” have a truth value and are therefore, propositions. In contrast, other sentences, such as “How are you doing?” (an interrogatory sentence), “Crikey! What a beautiful day!” (an exclamatory sentence) and “Come here.” (an imperative sentence) have no truth value and are not propositions.

Definition

Truth Value

A truth value is either true or false, abbreviated T and F, respectively.

Proposition

A proposition is a declarative sentence that has exactly one truth value. That is, it is either true or false. It is also called a statement.

Examples of sentences that are propositions

For instance, each of the following sentences is a proposition.

“ $7 \text{ is a prime number."}$

“Mars is the closest planet to the sun.”

“Two lines perpendicular to the same line are parallel to each other.”

These propositions have easily determined truth values.

The sentence, “Parts of New York City will be underwater by 2050.” is also a proposition, even though it will take years to determine its truth value. Similarly, sentences like “Cicero wrote for five hours every day.” are also propositions whose truth values may never be known.

Examples of sentences that are not propositions

The following sentences are not propositions. Can you guess why?

“She loves abstract algebra.”

This is a declarative sentence but unless we know to whom “she” refers, the sentence is neither true nor false and hence, does not qualify as a proposition.

“ $x > 3"$

This is also a declarative sentence but unless $x$ is assigned a value, the sentence is neither true nor false and hence, is not a proposition.

“This sentence is false.”

This is a declarative sentence that seems to have a truth value; however, it is not a proposition. Why? Suppose this sentence is true; this leads to a contradiction since the sentence would then be false. Conversely, if we suppose the sentence is false, then, because it states that it is false, the sentence must be true, which again results in a contradiction.

This illustrates an example of a paradox, a sentence that is neither true nor false and therefore is not considered a proposition.

This specific example is known as the “liar’s paradox,” which arises from the self-referential nature of the statement “This sentence is false.”

The study of paradoxes such as this has played a very important role in the development of modern mathematical logic.

Propositional Variable

We usually represent propositions with letters such as $p, q \text{ or } r$ . These letters are called propositional variables or statement variables.

Logical Connectives

Often, theorems are constructed by applying logical connectives to propositions to form new propositions. Such propositions are called compound propositions or compound statements. The truth value of a compound proposition depends on the truth values of its constituent propositions.

Negation, conjunction and disjunction are some examples of logical connectives.

Next, we will discuss the various logical connectives in detail.

Propositional Logic (or propositional calculus or zero-order logic)

Propositional logic is the study of logical statements (propositions) and their combinations using logical connectives.

Negation

Negation : If $p$ is a statement variable, the negation of $p$ is $\text{``not } p\text{''}$ , and is denoted by ${\thicksim} p$ . If $p$ is true, then ${\thicksim} p$ is false.

The negation ${\thicksim} p$ is also written as $p{'}, \bar{p} \text{ or } \neg p$ .

Conjunction

Conjunction : If $p$ and $q$ are statement variables, the conjunction of $p$ and $q$ is $\text{``}p \text{ and } q\text{''}$ , and is denoted by $p \wedge q$ . A conjunction is true only when both variables are true. If one or both variables are false, then $p \wedge q$ is false.

Disjunction

Disjunction : If $p$ and $q$ are statement variables, the disjunction of $p$ and $q$ is $\text{``}p \text{ or } q\text{''}$ , and is denoted by $p \vee q$ . A disjunction is true if one or both variables are true. $p \vee q$ is false only if both variables are false.

Exclusive Or (XOR)

Exclusive or (Exclusive Disjunction or xor) : If $p$ and $q$ are statement variables, the exclusive or or exclusive disjunction of $p$ and $q$ is $\text{``}p \text{ xor } q\text{''}$ , and is denoted by $p \oplus q$ or $p \veebar q$ . An exclusive disjunction is true if only one of the two variables is true. $p \oplus q$ is false only if both variables are true or both variables are false.

Simple Statements

A statement is simple or atomic if it cannot be syntactically divided into smaller parts; it is usually represented by a single statement variable and contains no logical connective.

Compound Statements

A statement is compound if it contains one or more logical connectives.

The symbols $\wedge$ (logical AND), $\vee$ (logical OR)and $\sim$ (logical NOT) are used to build complicated logical statements out of simpler ones.

Let $p = \text{``Marie likes abstract algebra.''}$ and let $q = \text{``Marie likes real analysis.''}$ , then the statement “Marie likes abstract algebra but not real analysis” can be written symbolically as:

p \wedge {\sim}q

Note that when translating English sentences to logical form, “but” generally means the same as “and”.

Let us do one more example.

“I can eat sugar or I can be healthy, but I cannot eat sugar and be healthy.” can be symbolically written as:

(p \vee q) \wedge {\sim}(p \wedge q)

Here, $p = \text{``I eat sugar''}$ and let $q = \text{``I'm healthy''}$ ; note that all operations within parenthesis are performed first.

Tautology

A tautology is a compound statement (proposition) that is always true, regardless of the truth values of its underlying atomic statements.

For example, the statement $\mathcal{p \vee {\sim} p}$ is a tautology.

Contradiction (or self-contradiction)

A contradiction is a compound statement that is always false, regardless of the truth values of its underlying atomic statements.

For example, the statement $\mathcal{p \wedge {\sim} p}$ is a contradiction.

Logical Form

The lexical semantics of a statement is not the same as its logical semantics, i.e., the content of a statement is not the same as its logical form.

Consider the following two statements.

If Marie eats pizza everyday, she will be fat. Therefore, if Marie is thin, she does not eat pizza everyday.

If $x$ is a positive real number such that $x = 2$ , then $x^2 = 4$ . Therefore, if $x^2 = 4$ , then $x = 2$ .

While the content of the two above statements is different, their logical form is similar.

It should be noted that the logical analysis of an argument does not prove its validity. It only helps to analyze an argument’s form to determine if the truth of the argument’s conclusion follows from the truth of the preceding statements i.e., it helps to detect non sequiturs.

In our first argument, logical analysis does not prove that if Marie eats pizza she will become fat. It only analyses whether the truth of the conclusion “if Marie is thin, she does not eat pizza everyday.” follows from the truth of the preceding statement, namely, “If Marie eats pizza everyday, she will be fat.”.

Let the statement variable $p$ represent the statements “Marie eats pizza everyday” and $\text{``} x$ is a positive real number such that $x = 2 \text{''}$ .

Let the statement variable $q$ represent the statements “Marie is fat” and $\text{``} x^2 = 4 \text{''}$ .

Then the common form for the above two arguments is:

\begin{equation*} \begin{split} & \text{If p, then q.} \\ & \text{Therefore, if not q, then not p.} \end{split} \end{equation*}

Truth Table

Since a statement must be either true or false but not both, it should have a well defined truth value. The truth of a statement can be expressed by a Truth Table.

A truth table for a given statement displays the resulting truth values for various combinations of truth values for the variables. The truth of a compound statement can be logically derived by using the known truth values for various parts of a statement.

The following is the truth table for negation ( ${\sim} p$ ) ,conjunction $(p \wedge q)$ , disjunction $(p \vee q)$ and exclusive or $(p \oplus q)$ , where $p \text{ and } q$ are statement variables. In the truth table $\mathcal{'T'}$ denotes ‘True’ and $\mathcal{'F'}$ denotes ‘False’.

As an aside, the truth table shows us that the “XOR” operation results in “T” and “F” with equal probabilities. As we will see in future discussions, this property of “XOR” is well exploited in cryptography.

Logical Equivalence

Two statements are logically equivalent if and only if their resulting forms are the same when identical statement variables are used to represent their component statements.

Consider the following two statements:

If Marie eats pizza everyday, she will become fat.

If $x$ is a positive real number such that $x = 2$ , then $x^2 = 4$ .

These two statements are logically equivalent since they have a common form, namely,

\text{If p, then q.}

Here statement variable $p$ stands for “Marie eats pizza everyday” and $\text{``}x$ is a positive real number such that $x = 2\text{''}$ and statement variable $q$ stands for “Marie will become fat” and $\text{``}x^2 = 4\text{''}$ .

Two statement forms are logically equivalent if and only if their resulting truth tables are identical for each variation of statement variables.

Logical equivalence of two compound statements $\mathcal{p \text{ and } q}$ is denoted by $\mathcal{p \equiv q \text{ or } p\Leftrightarrow q \text{ or } p \text{ iff } q}$ .

The following truth table shows that $(\mathcal{p \vee q}) \wedge {\sim}(\mathcal{p \wedge q})$ is logically equivalent to $\mathcal{p \oplus q}$ since they have the same truth values i.e., $\mathcal{p \text{ xor } q}$ is equivalent to $\text{``} p \text{ or } q$ but not both $p \text{ and } q \text{''}$ . An $\text{xor}$ is used to express mutually exclusive events; one of the two events can occur but not both. For example, “I can be in Paris or Rome, but I cannot be in Paris and Rome at the same time.”

To test for logical equivalence of two statements, construct a truth table that includes every variable to be evaluated, and then check whether the resulting truth values of the two statements are equivalent.

Logical equivalencies can be used to simplify statement forms and to confirm or disprove an equivalency. To simplify an equivalency, start with one side of the equation and attempt to replace sections of it with equivalent expressions.

DeMorgan’s Laws

Suppose a modeling agency runs an ad stating “Please do not apply if you are both tall and thin.” How does this modeling agency go about selecting models?

There are four possible groups of people :

Models who are only tall but not thin
Models who are only thin but not tall
Models who are both tall and thin
Models who are neither tall nor thin

We can see that all groups except group $3$ are eligible to apply.

Since exclusion of group $3$ is equivalent to the inclusion of groups $1, 2 \text{ and }4$ , there are two logically equivalent ways to express the condition of not choosing models who are both tall and thin.

Let us logically express this condition through the exclusion of group $3$ .

If statement variable $p$ represents “Models who are tall” and statement variable $q$ represents “Models who are thin”, then the exclusion of group $3$ i.e., “not both tall and thin” can be represented as ${\sim}\mathcal{(p \wedge q)}$ .

Now let us logically express the same condition through the inclusion of groups $1, 2 \text{ and } 4$ . “Not Tall” includes groups $2 \text{ and } 4$ and “Not Thin” includes groups $1 \text{ and } 4$ ; hence “Not Tall or Not Thin” includes groups $1, 2 \text{ and } 4$ .Therefore the condition can be expressed as $\mathcal{{\sim}p \vee {\sim}q}$ .

Hence ${\sim}\mathcal{(p \wedge q)}$ is logically equivalent to $\mathcal{{\sim}p \vee {\sim}q}$ .

The following truth table expresses this logical equivalence.

The following is an illustration of this logical equivalence through a venn diagram.

The following is the representation of the same logical equivalence in terms of sets. The $\cap$ (intersection) corresponds to $\wedge$ (logical AND), the $\cup$ (union) corresponds to $\vee$ (logical OR) and the ${'}$ corresponds to ${\sim}$ (negation).

Now suppose a competing modeling agency runs an ad stating “Please don’t apply if you are either tall or thin.” So who are the people eligible to apply? Looking at the list of people enumerated as groups, we can see that only group $4$ is eligible to apply. The inclusion of group $4$ is equivalent to the exclusion of the other groups, namely, groups $1, 2 \text{ and } 3$ . Let us now express these logically.

Since the inclusion of group $4$ means selecting models who are neither tall nor thin, we can express this logically as ${\sim} \mathcal{(p \vee q)}$ .

Another equivalent way to select models who are neither tall nor thin is to exclude groups $1, 2 \text{ and } 3$ . ${\sim} \text{Tall}$ excludes groups $1 \text{ and } 3$ and ${\sim} \text{Thin}$ excludes groups $2 \text{ and } 3$ . Hence ${\sim} \text{Tall} \wedge {\sim} \text{Thin}$ will exclude groups $1, 2 \text{ and } 3$ . Expressing this in terms of statement variables $p \text{ and } q$ , results in ${\sim} p \wedge {\sim} q$ , where $p$ represents “Models who are tall” and $q$ represents “Models who are thin”.

The following truth table confirms the logical equivalence of ${\sim} \mathcal{(p \vee q)}$ and ${\sim} p \wedge {\sim} q$ .

The following is an illustration of this logical equivalence through a venn diagram.

The following is the representation of the same logical equivalence in terms of sets.

The above two logical equivalences are called DeMorgan’s Laws; it connects conjunctions and disjunctions through negations. It is used to simplify compound statement forms into simpler ones.

We will close this discussion by restating these laws:

The negation of a conjunction (logical AND) of two statements is logically equivalent to the disjunction (logical OR) of each statement’s negation. Expressed symbolically,

${\sim} \big(p \wedge q\big) \equiv {\sim} p \vee {\sim} q$ , where $p \text{ and } q$ are statement variables.
The negation of a disjunction of two statements is logically equivalent to the conjunction of each statement’s negation i.e., “not (A or B)” is logically equivalent to “not A and not B”. Expressed symbolically,

${\sim} \big(p \vee q \big)\equiv {\sim} p \wedge {\sim} q$ , where $p \text{ and } q$ are statement variables.

NOT-AND (NAND)

NAND : If $p$ and $q$ are statement variables, the negation of the conjunction of $p$ and $q$ is $\text{``}p \text{ nand } q\text{''}$ , and is denoted by $p \mid q$ .

$p \mid q$ means $\text{``}p \text{ and } q\text{ are not both true''}$ .

$p \mid q$ is true only if at least one of the two variables is false. It is false if both variables are true.

Hence,

p \mid q \equiv {\sim} \big(p \wedge q\big) \equiv {\sim}p \vee {\sim} q

The right most logical equivalence follows from De Morgan’s law.

The negation of the statement variable $p$ and the conjunction and disjunction of statement variables $p$ and $q$ can be expressed by just the nand connective.

The negation of $p$ can be expressed in terms of nand as follows:

\begin{equation*} \begin{split} {\sim}p & \equiv {\sim}\big(p \wedge p\big) \\ & \equiv p \mid p \end{split} \end{equation*}

The conjunction of $p$ and $q$ can be expressed in terms of nand as follows:

\begin{equation*} \begin{split} p \wedge q & \equiv {\sim}\Big({\sim}\big(p \wedge q\big)\Big) \\ & \equiv \Big({\sim}\big(p \wedge q\big)\Big) \mid \Big({\sim}\big(p \wedge q\big)\Big) \\ & \equiv \big(p \mid q\big) \mid \big(p \mid q\big) \\ \end{split} \end{equation*}

The disjunction of $p$ and $q$ can be expressed in terms of nand as follows:

\begin{equation*} \begin{split} p \vee q & \equiv \Bigg({\sim}\Big({\sim}\big(p \wedge p\big)\Big)\Bigg) \vee \Bigg({\sim}\Big({\sim}\big(q \wedge q\big)\Big)\Bigg) \\ & \equiv \Big({\sim}\big(p \mid p \big)\Big) \vee \Big({\sim}\big(q \mid q \big)\Big) \\ & \equiv \big(p \mid p \big) \mid \big(q \mid q \big) \end{split} \end{equation*}

NOT-OR (NOR)

NOR : If $p$ and $q$ are statement variables, the negation of the disjunction of $p$ and $q$ is $\text{``}p \text{ nor } q\text{''}$ , and is denoted by $p \downarrow q$ . $p \downarrow q$ means $\text{``neither } p \text{ nor } q \text{''}$ .

$p \downarrow q$ is true only if both the variables are false. It is false if at least one variable is true.

From De Morgan’s Law it follows that

p \downarrow q \equiv {\sim} \big(p \vee q\big) \equiv {\sim}p \wedge {\sim} q

As was the case with nand, we can express negation, conjunction and disjunction in terms of the nor connective.

The negation of statement variable $p$ can be expressed in terms of the nor connective as follows:

\begin{equation*} \begin{split} {\sim}p & \equiv {\sim}\big(p \vee p\big) \\ & \equiv p \downarrow p \end{split} \end{equation*}

The conjunction of $p$ and $q$ can be expressed in terms of nor as follows:

\begin{equation*} \begin{split} p \wedge q & \equiv \Bigg({\sim}\Big({\sim}\big(p \vee p\big)\Big)\Bigg) \wedge \Bigg({\sim}\Big({\sim}\big(q \vee q\big)\Big)\Bigg) \\ & \equiv \Big({\sim}\big(p \downarrow p \big)\Big) \wedge \Big({\sim}\big(q \downarrow q \big)\Big) \\ & \equiv \big(p \downarrow p \big) \downarrow \big(q \downarrow q \big) \end{split} \end{equation*}

The disjunction of $p$ and $q$ can be expressed in terms of nor as follows:

\begin{equation*} \begin{split} p \vee q & \equiv {\sim}\Big({\sim}\big(p \vee q\big)\Big) \\ & \equiv \Big({\sim}\big(p \vee q\big)\Big) \downarrow \Big({\sim}\big(p \vee q\big)\Big) \\ & \equiv \big(p \downarrow q\big) \downarrow \big(p \downarrow q\big) \\ \end{split} \end{equation*}

Logical Identity

A logical equivalence that is frequently used is sometimes called a logical identity.

The following is a table enumerating various logical identities that can help reduce compound statements to simpler forms.

Given statement variables $p, q \text{ and } r$ , a tautology $t$ and a contradiction $c$ , the following logical equivalences hold:

Let us consider the following example as an illustration of how logical identities can help simplify compound statements.

We will prove that $\mathcal{\Bigg(\Big({\sim}\big(p \vee {\sim} q \big)\Big) \wedge q \Bigg) \vee \big( p \wedge q \big) \equiv q}$ .

\begin{equation*} \begin{split} \Bigg(\Big({\sim}\big(p \vee {\sim} q \big)\Big) \wedge q \Bigg) \vee \big( p \wedge q \big) & \equiv \Bigg( \Big({\sim}p \wedge {\sim}\big({\sim}q\big)\Big) \wedge q \Bigg) \vee \big( p \wedge q \big) \quad \big( \textit{By De Morgan's Law}\big) \\ & \equiv \Big(\big({\sim}p \wedge q\big) \wedge q \Big) \vee \big( p \wedge q \big) \quad \quad \quad\quad\big(\textit{By Double Negation Law}\big) \\ & \equiv \Big({\sim}p \wedge \big(q \wedge q \big)\Big) \vee \big( p \wedge q \big) \quad \quad \quad\quad\big(\textit{By Associative Law}\big) \\ & \equiv \big({\sim}p \wedge q \big) \vee \big( p \wedge q \big) \quad \quad \quad \quad \quad \quad\,\,\,\,\big(\textit{By Idempotent Law}\big) \\ & \equiv \big(q \wedge {\sim}p \big) \vee \big( q \wedge p \big) \quad \quad \quad \quad \quad \quad\,\,\,\,\big(\textit{By Commutative Law}\big) \\ & \equiv q \wedge \big({\sim}p \vee p\big) \quad \quad \quad \quad \quad \quad\quad\quad\quad\,\,\big(\textit{By Distributive Law}\big) \\ & \equiv q \wedge \big(p \vee {\sim}p\big) \quad \quad \quad \quad \quad \quad\quad\quad\quad\,\,\big(\textit{By Commutative Law}\big) \\ & \equiv q \wedge t \quad \quad \quad \quad \quad \quad\quad\quad\quad\quad\quad\quad\,\,\,\,\, \big(\textit{By Negation Law}\big) \\ & \equiv q \quad \quad \quad \quad \quad \quad\quad\quad\quad\quad\quad\quad\quad\,\,\,\,\,\,\,\, \big(\textit{By Identity Law}\big) \\ \end{split} \end{equation*}

As we can see, the use of logical identities resolves the hairy compound statement to a single statement variable.