1.1 Propositional Logic

Propositions and Quantifiers

A proposition is a logical statement which is either true or false. Propositions may be joined together to form propositional forms. We can join two propositions $P$ and $Q$ in the following basic ways:

1. Conjunction: $P\wedge Q$ (”$P$ and $Q$”). True only when both $P$ and $Q$ are true.
2. Disjunction: $P\vee Q$ (”$P$ or $Q$”). True when either (or both) $P$ or $Q$ are true.
3. Negation: $\neg P$ (“not $P$”). True only when $P$ is false.

Understanding

There are many more propositional forms, such as XOR (“Exclusive Or,” denoted $\oplus$) and NAND (“Not And”). However, any other propositional form may be constructed using one or more of the previously defined fundamental forms. Let’s take a step back from defining any more forms and describe a comprehensive truth table for the two more complex forms:

\begin{document}
\begin{tikzpicture}
 
% Draw the table borders
\draw (0,0) -- (8,0);
\draw (0,-1) -- (8,-1);
\draw (0,-2) -- (8,-2);
\draw (0,-3) -- (8,-3);
\draw (0,-4) -- (8,-4);
\draw (0,-5) -- (8,-5);
 
\draw (0,0) -- (0,-5);
\draw (2,0) -- (2,-5);
\draw (3.95,0) -- (3.95,-5);
\draw (4.05,0) -- (4.05,-5);
\draw (6,0) -- (6,-5);
\draw (8,0) -- (8,-5);
 
% Add the table content
\node at (1, -0.5) {$\textbf{P}$};
\node at (3, -0.5) {$\textbf{Q}$};
\node at (5, -0.5) {$\textbf{P} \land \textbf{Q}$};
\node at (7, -0.5) {$\textbf{P} \lor \textbf{Q}$};
 
\node at (1, -1.5) {F};
\node at (3, -1.5) {F};
\node at (5, -1.5) {F};
\node at (7, -1.5) {F};
 
\node at (1, -2.5) {T};
\node at (3, -2.5) {F};
\node at (5, -2.5) {F};
\node at (7, -2.5) {T};
 
\node at (1, -3.5) {F};
\node at (3, -3.5) {T};
\node at (5, -3.5) {F};
\node at (7, -3.5) {T};
 
\node at (1, -4.5) {T};
\node at (3, -4.5) {T};
\node at (5, -4.5) {T};
\node at (7, -4.5) {T};
 
\end{tikzpicture}
\end{document}

The truth table for negation is fairly straightforward, and does not require a graph in this note.

Properties

(DeMorgan’s Laws) $\neg (P\wedge Q)\equiv (\neg P\vee \neg Q)$, and $\neg (P\vee Q)\equiv (\neg P\wedge \neg Q)$.

Examples

Propositional Practice

Convert the following English sentences into propositional logic. State whether the statement is true or false with a brief justification.

There is a real number which is not rational. $(\exists x\in \mathbb{R})(x\notin \mathbb{Q})$. This is true, for example $\sqrt{2}$ or $\pi$.

The solution is

All integers are natural numbers or are negative, but not both (XOR). $(\forall x\in \mathbb{Z})(((x\in \mathbb{N})\vee (x<0))\wedge \neg ((x\in \mathbb{N})\wedge (x<0)))$. This is true, since we can define $0$ to be part of the naturals.

This is translated as

If a natural number is divisible by 6, it is divisible by 2 or it is divisible by 3. $(6\mid x)⟹(2\mid x)\vee (3\mid x)$. This is true, since for all natural numbers $x$, $x=6k=2(3k)=3(2k)$.

We can convert this as

Now convert the following propositions into English sentences.

$\neg (\forall x\in \mathbb{Q})(x\in \mathbb{Z})$ Since the negation applies to the statement rather the domain, $\neg (\forall x\in \mathbb{Q})(x\in \mathbb{Z})\equiv (\exists x\in \mathbb{Q})(x\notin \mathbb{Z})$, which translates to "There exists a rational number that is not an integer." This is trivially true, since we have numbers such as $0.5$.

$(\forall x\in \mathbb{Z})(((2\mid x)\vee (3\mid x))⟹(6\mid x))$ This means that "If any integer is divisible by two or three, then the integer is also divisible by six." This is false, since 2 and 3 are not divisible by 6.

$(\forall x\in \mathbb{N})((x>7)⟹((\exists a,b\in \mathbb{N})(a+b=x)))$ This statement directly translates to "If a natural number greater than 7 can be expressed as the sum of two other naturals." This is trivially true, since in one case we can write $a=x$ and $b=0$.

Constructing XOR

XOR is also known as “Exclusive OR” in plain English. It is not true when both $P$ and $Q$ are true. Let’s construct it: