Saturday, October 21, 2017

propositional logic

Some notes for the Stanford class "Introduction to Mathematical Thinking".

Propositional logic is the branch of logic concerned with the study of propositions (whether they are true or false) that are formed by other propositions with the use of logical connectives, and how their value depends on the truth value of their components.

The following is an example of a very simple inference within the scope of propositional logic:
Premise 1: If it's raining then it's cloudy.
Premise 2: It's raining.
Conclusion: It's cloudy.
Both premises and the conclusion are propositions. 

This inference can be restated replacing those atomic statements with statement letters, which are interpreted as variables representing statements:


Premise 1: 
Premise 2: 
Conclusion: 

Mathematicians sometimes distinguish between propositional constants, propositional variables, and schemata. Propositional constants represent some particular proposition, while propositional variables range over the set of all atomic propositions. Schemata range over all propositions and are commonly represented with Greek letters, most often φψ, and χ.

Conjunction is a truth-functional connective which forms a proposition out of two simpler propositions, for example, P and Q. The conjunction of P and Q is written P ∧ Q, and expresses that each are true.

Disjunction resembles conjunction in that it forms a proposition out of two simpler propositions. We write it P ∨ Q, and it is read "P or Q". It expresses that either P or Q is true.

Implication (also known as material conditional) also joins two simpler propositions, and we write P → Q, which is read "if P then Q". The proposition to the left of the arrow is called the antecedent and the proposition to the right is called the consequent. (There is no such designation for conjunction or disjunction, since they are commutative operations.) It expresses that Q is true whenever P is true. 

The material conditional can yield some unexpected truths when expressed in natural language. For example, any material conditional statement with a false antecedent is true (see vacuous truth). So the statement "if 2 is odd then 2 is even" is true. Similarly, any material conditional with a true consequent is true. So the statement "if I have a penny in my pocket then Paris is in France" is always true, regardless of whether or not there is a penny in my pocket.

In the statement "it is necessary that Q in order for P", P is the antecedent and Q the consequent.