Propositional Logic: Propositions, Connectives and Valid Formulae

Hello students, welcome to Kwickprep. If it rains, the match is cancelled. Is that sentence true, false, or does it depend? Logic lets us decide with a table, not an argument. Today we learn propositions, connectives, truth tables, and the words tautology, contradiction, satisfiable and valid.

A proposition is a statement that is either true or false, but not both. Delhi is in India is a proposition, and it is true. Seven is even is also a proposition, even though it is false. Close the door is a command, so it has no truth value. Is it five pm is a question, so it is not a proposition. And x is greater than three is not a proposition, until we know the value of x.

Propositions come in two kinds. A simple proposition states one idea, and we name it with a small letter like p, q or r. For example, p is it is raining, and q is the match is cancelled. A compound proposition joins simple ones using connectives, which are words like and, or, not. Its truth value is written T for true or F for false, just like one and zero in logic gates.

There are five logical connectives. Negation, written with a tilde, means not p, and it flips the truth value. Conjunction, written with an upside down v, means p and q. Disjunction, written with a v, means p or q. The conditional, written with an arrow, means if p then q. The biconditional, a double arrow, means p if and only if q. Some books use other symbols, such as a double-lined arrow for implies, but the meanings are the same.

Let us build truth tables row by row. With two propositions there are four rows. Row one: both are true, so and is true, and or is true. Row two: p is true, q is false, so and is false, but or is true. Row three: again and is false, and or is true. Row four: both are false, so both columns are false.

The conditional needs care, so let us use a promise. Suppose p is you score ninety, and q is you get a new cycle. Row one: you score ninety and get the cycle, so the promise is kept, true. Row two: you score ninety but get no cycle, so the promise is broken, false. Rows three and four: you did not score ninety, so the promise was never broken, and the conditional is true. The biconditional is true only when both sides have the same value, as in rows one and four.

Now a compound statement, not p or q, with a helper column for not p. Row one: p is true, so not p is false, and false or true is true. Row two: not p is false and q is false, so the result is false. Row three: not p is true, so the result is true. Row four: not p is true, so the result is true. Compare the last column with p arrow q. They match in every row, so the two statements are logically equivalent.

Two rules help with longer statements. Negation is applied first, then and, then or, and the arrows come last. When in doubt, add brackets, because they make the order clear. Each extra proposition doubles the rows, so two need four rows. Three propositions need eight rows, from all true down to all false.

Every compound statement falls into one of three types, decided by its last column. A tautology is true in every row, like p or not p, since it is either raining or not. A contradiction is false in every row, like p and not p, since it cannot rain and not rain at once. A contingency is true in some rows and false in others, like p arrow q, which we just saw.

Let us test a statement row by row: p and q, arrow p. Row one: p and q is true, and p is true, so the arrow is true. Row two: p and q is false, and an arrow from false is always true. Row three: p and q is false, so the arrow is true. Row four: again it starts from false, so it is true. The last column is all T, so this statement is a tautology.

Pause the video and decide. The statement is p arrow not p. Is it a tautology, a contradiction or a contingency? When p is true, it is true arrow false, which is false. When p is false, it is false arrow true, which is true. One T and one F, so it is a contingency.

Your syllabus also uses three more words for well formed formulae. A well formed formula is simply a correctly written statement using propositions, connectives and brackets. A formula is valid if it is true in every row, so valid means tautology. It is satisfiable if at least one row makes it true, so tautologies and contingencies are both satisfiable. It is unsatisfiable if no row makes it true, which is exactly a contradiction.

Here is a trap that costs marks. Every valid formula is also satisfiable, because true in all rows means true in at least one. But a satisfiable formula need not be valid. For example, p arrow q is true in three rows, so it is satisfiable. But it fails in row two, so it is not valid. And p and not p is true in no row, so it is unsatisfiable, and therefore not valid either.

Let us revise what we learned today. A proposition is a statement that is either true or false. The five connectives are not, and, or, if then, and if and only if. The conditional is false only when p is true and q is false. A tautology is all true, a contradiction is all false, and a contingency is mixed. Valid means tautology, unsatisfiable means contradiction, and satisfiable means at least one true row.