$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 3.1: Propositional Logic is Not Enough

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

Consider the following deduction:

Merlin is a wizard. All wizards wear funny hats.
Therefore, Merlin wears a funny hat.

To symbolize it in Propositional Logic, we define a symbolization key:

$$W$$: Merlin is a wizard.
$$A$$: All wizards are wearing funny hats.
$$H$$: Merlin is wearing a funny hat.

Now we symbolize the deduction:

Hypotheses:

$$W$$
$$A$$

Conclusion: $$H$$

This is not valid in Propositional Logic. (If $$W$$ and $$A$$ are true, but $$H$$ is false, then it is obvious that both hypotheses are true, but the conclusion is false.) There is something very wrong here, because the deduction that was written in English is clearly valid.

The problem is that symbolizing this deduction in Propositional Logic leaves out some of the important structure: The assertion “All wizards are wearing funny hats” is about both wizards and hat-wearing, but Propositional Logic is not able to capture this information: it loses the connection between Merlin’s being a wizard and Merlin’s wearing a hat. However, the problem is not that we have made a mistake while symbolizing the deduction; it is the best symbolization we can give for this deduction in Propositional Logic.

In order to symbolize this deduction properly, we need to use a more powerful logical language. This language is called First-Order Logic, and its assertions are built from “predicates” and “quantifiers.”

A predicate is an expression like “_______ is wearing a funny hat.” This is not an assertion on its own, because it is neither true nor false until we fill in the blank, to specify who it is that we claim is wearing a funny hat.

The details of this will be explained in Section $$3.2D$$, but here is the basic idea: In First-Order Logic, we will represent predicates with capital letters. For instance, we could let $$H$$ stand for “_______ is wearing a funny hat.” However, we will use variables instead of blanks; so “$$x$$ is wearing a funny hat” is a predicate, and we could represent it as $$H(x)$$.

The words “all” and “some” are quantifiers, and we will have symbols that represent them. For instance, “$$\exists$$” will mean “There exists some ______, such that.” Thus, to say that someone is wearing a funny hat, we can write $$\exists x ,H(x)$$; that is: There exists some $$x$$, such that $$x$$ is wearing a funny hat. Quantifiers will be dealt with in Chapter $$4$$, when First-Order Logic is fully explained.

With predicates and quantifiers, we will be talking about many people (or other things) all at once, instead of one at a time. For example, we may wish to talk about “the people who are wearing hats,” or “the mammals that lay eggs.” These are examples of sets.