Propositional Logic - Semantics

Now that we have developed a syntax for this language, we can apply meaning to well formed fomulas. We denote truth as $ \top $ and false as $ \bot $. So let $ t $ be a truth function defined as $$ t : \mathcal{F} \rightarrow \{\top,\bot\} $$ where $ \mathcal{F} $ is the set of well formed formulas. Alternatively let $ \phi,\psi $ be well formed formulas, and we have

Negation

φ	¬ φ
⊤	⊥
⊥	⊤

Conjunction

φ	ψ	φ ∧ ψ
⊤	⊤	⊤
⊤	⊥	⊥
⊥	⊤	⊥
⊥	⊥	⊥

Disjunction

φ	ψ	φ ∨ ψ
⊤	⊤	⊤
⊤	⊥	⊤
⊥	⊤	⊤
⊥	⊥	⊥

Implication

φ	ψ	φ → ψ
⊤	⊤	⊤
⊤	⊥	⊥
⊥	⊤	⊤
⊥	⊥	⊤

So we have that conjunction is only true in the case where both of the operands are true. Disjunction is kind of the same, just opposite. That is disjunction is false only in the case where both operands are false. We call this type of disjunction for inclusive. The exclusive one is false in two cases, that is the case where both operands are false, and the case where both operands are true. The exclusive one might seem the more intuitive one: "I have a cat or I have a dog" often is interpreted as "I" have exactly one of them. However we use the inclusive version in basic logic. So we have that "I gave you 100 money or I gave you 200 money" is true in the case where "I" gave you 300 money. The implication is kind of an odd one. Especially the case where false implies true. So I state "If it rains today, my outdoor plants will be watered today". However we do not have rain today, so my plants may be watered, they may not. That "true implies false" is false is easier to develop intution about. Given that I state the above statement, and given that it does rain, but my plants are not watered, the statement seems quite absurd.

A truth table with only $ \top $ in the last column is called a tautology. One with only $ \bot $ is called a contradiction. One with a mix of both is called contingent. As mentioned above we have different relationships between the connectives. For example we have that $ \neg (\neg \phi \lor \neg \psi) $ is the same as $ \phi \land \psi $. We can prove this using these truth tables. First we introduce a new connective called biimplication, we use $ \leftrightarrow $ for this. A biimpliction is an implication that goes both ways, the truth table is given as

Biimplication

φ	ψ	φ ↔ ψ
⊤	⊤	⊤
⊤	⊥	⊥
⊥	⊤	⊥
⊥	⊥	⊤

If we have that $ \phi \leftrightarrow \psi $ is a tautology, then we say that these two formulas are logically equivalent. We write this as $ \phi \equiv \psi $. Note that two formulas are logically equivalent if and only if they have the same truth table. We list the truth table for the formula above

φ	ψ	¬ φ ∨ ¬ ψ	¬ (¬ φ ∨ ¬ ψ)
⊤	⊤	⊥	⊤
⊤	⊥	⊤	⊥
⊥	⊤	⊤	⊥
⊥	⊥	⊤	⊥

And hence we have that $$ \phi \land \psi \equiv \neg (\neg \phi \lor \neg \psi) $$

Entailment

Given a set of formulas, $ \Phi = \phi_1, \phi_2, \dots $, we say that this set entails some formula $ \psi $, if whenever every formula in $ \Phi $ is true, so is $ \psi $. We use $ \vDash $ for entailment. We call the set $ \Phi $ for premises, and we call $ \psi $ the conclusion. Formally we write $$ \phi_1 , \phi_2 , \dots \vDash \psi $$ Both $ \equiv $ and $ \vDash $ are symbols that are not part of our logic syntax, therefore we call them meta symbols. As an example of entailment we have a deductive argument form called modus ponens. It goes as, I know that $ p $ implies $ q $, I know that $ p $ is true, therefore $ q $ is true. We can write it in the above formulation style: $$ p \rightarrow q, p \vDash q $$ Entailment can be stated within our logical framework as whether the following implication (in general) is a tautology: $$ ((p \rightarrow q) \land p) \rightarrow q $$ We can do the truth table, the result is:

p	q	(p → q) ∧ p	((p → q) ∧ p) → q
⊤	⊤	⊤	⊤
⊤	⊥	⊥	⊤
⊥	⊤	⊥	⊤
⊥	⊥	⊥	⊤

Constructing Truth Tables

This task is quite cumbersome. The next chapter is about natural deduction which is a proof system. It is so that anything that can be shown to entail within these truth tables (semantically), can be proven in this proof system. And vice versa. Alternatively the root of this webpage brkmnd.com is a terminal. It has a build in truth table constructor. You can use it with command prop2table "expr" where expr is some logical expression. Here ~,/\,\/,-> are used as negation, conjunction, disjunction resp. implication.