Logical Implication

Definition. A formula $P$ logically implies a formula $Q$ if and only if for all Boolean valuations, if $[P]=T$ then $[Q]=T$.

$P\models Q$

which is pronounced “P entails Q” or “P logically implies Q”.

$P\models Q$ iff $\models P\Rightarrow Q$ iff $P\Rightarrow Q$ is a tautology. (where the meta-symbols are in black and the formulas are in red and substituting some formulas for P and Q)

So |= P means true |= P.

Valid Arguments

Definition. An argument is a valid argument if in all Boolean valuations where the premises have the value $T$, the conclusion has the truth value $T$. $P_1,P_2,\dots ,P_n\models C$

• $P_1,P_2,\dots ,P_n$ are premises
• $C$ is the conclusion

An argument is valid if and only if the conjunction of the premises logically imply the conclusion.

$\models P$ means formula $P$ is a tautology. We can also say $P$ is “valid” to mean $P$ is a Tautology.

To prove an valid argument, with:

• Transformational Proof: Assume premises, and them together, and arrive to the conclusion, i.e. $P_1,P_2,\dots |=Q$
• Natural Deduction: Just whatever the argument is
• Semantic Tableaux: Use the premises and the negation of the conclusion.

Invalid Arguments

Definition. An argument is invalid if and only if there is at least one Boolean valuation in which the premises are $T$, but the conclusion is $F$.

To show that an argument is invalid, find a counterexample: a Boolean valuation where the premises are $T$ and the conclusion is $F$.

• Natural Deduction: Have the premises and conclude False, i.e $P_1,P_2,\dots ,P_n|-false$

What about Logical Equivalence

See page 110 of the notes. (not to be confused), the above is stronger

Remember that |= is not ⇚⇛. The formula C can be “weaker” than the conjunction of the premises. “Weaker” means T in more Boolean valuations.

For example, $a\wedge b\models a\vee b$ The formula a ∨ b is T in some Boolean valuations where a ∧ b is not T.