Symbols: ¬ → ↔ ᴧ ☐ Φ ♢∀ ∃
Connectives:
P→Q Implication P only if q
if P then Q
P therefore Q
P implies Q
Even if P, Q
If A then B = A→B = B if A <- Special case
Note they are swapped around if you only use ‘if’
Only if P, Q can be re-written as Q only if P which translates to Q→P
Only false when the 1st one (left of the → symbol) is true and the other one
is false
↔ Bi-condition P if and only if Q
ᴧ Conjunction (AND) and
but
however
v Disjunction (OR) or
either P or Q (¬ v)
Neither P nor Q
Means ¬P ᴧ ¬Q which can be simplified to ¬(P v Q)
,‘UNLESS’ example:
Unless you apply the brakes, you will crash
So if you NOT crash then it means you applied the brakes.
Means:
If NOT crashed, then braked.
If NOT braked, then Crashed.
Say we let Q be ‘applied the breaks’ and P be ‘you crash’
Then
Unless Q, then P
If NOT P, then Q
If NOT Q, then P
Sequent structure:
How to show if a sequent is valid or not valid:
A valuation of a formula is an assignment of each propositional atom to a truth table.
Identify the premises and the conclusion
Construct a truth table showing the truth values of the premises and the
conclusion
Look for all the rows where the premises are all true - we call such rows
critical rows. If the conclusion is false in a critical row, then the argument
, is invalid. Otherwise, the argument is valid (since the conclusion is
always true when the premises are true).
e.g.
HORN formula steps are:
1. Mark all T’s true if it occurs in the list
2. If everything on the left of the → is marked then mark the right as well
and also mark all instances of what was on the right and then go to step
2 again. Otherwise go to 3.
3. If contradiction is marked then Horn formula is unsatisfiable. Otherwise
go to 4.
4. Print out Horn formula is satisfiable and stop.
e.g.
,Step 1:
Step 2:
Step 2:
Step 2:
Step 3:
Contradiction is marked, thus Horn formula is not satisfiable.
Terms and WFF (Well formed formulas):
Variables, constants and functions are terms.
Well formed formulas (WFF)
To be well formed
, statements inside the brackets needs to be a term (variables, constants
or functions)
variables can’t stand alone without a capital letter/predicate. E.g. y
instead of P(y)
Not all variables need to be bound by a quantifier, i.e. a well formed
formula can have free variables.
Can’t use constant with quantifiers
WFF must have a predicate in them to be a WFF.
e.g.
Note you also have to take into account the information given like Q, S and P are
predicates with 2 variables. If they give those predicates with one argument then it is not
well formed.
Answers:
i) Not a WFF, because a quantifier can’t be inside the brackets of a predicate.
ii) Not a WFF, because a predicate can’t be inside another predicated brackets.
iii) It is a WFF.
iv) Not a WFF, because you can’t have quantifiers with constants.
v) Not a WFF (You are not allowed to have variable without predicate)
,Natural deduction
Rules:
Disjunction elimination
We have 2 sub proofs
Disjunction Introduction
If P is present then you can deduce that
Universal Quantifier Elimination:
Example:
, - WE assume variable inside block.
- Anywhere in this block we allowed to eliminate with the variables
becoming the variable chosen.
WORDING: If it is true for any variable then it must be true for a certain
variable.
Universal quantifier introduction:
Example:
- Introduce a variable
- Then if we find a WFF for that variable then we can introduce for
that WFF.
- Note the introduction happens outside the block where you introduced
the variable.
,We say for any arbiter variable chosen and we find that a WFF is true, then
WFF must be true for all variables
Existential quantifier introduction:
Example:
- If you have WFF with a variable inside the block then you can introduce
inside the block for that WFF.
- It can be introduced outside the block as well
Here we saying that if an variable exist for WFF then it is true for some (∃)
variable.
Existential quantifier elimination
This is the longest one.
Example:
, Note:
- You make an assumption of premise (or statement) that you want to
remove by replacing variable with arbitrary variable. Black arrow in picture
- Then from the assumption you get to any WFF. Blue line in picture
Then you allowed to introduce that WFF using elimination rule. Red line in
picture.
Example showing proof by contradiction and also how to do negation
elimination. i.e. contradiction intro.
Connectives:
P→Q Implication P only if q
if P then Q
P therefore Q
P implies Q
Even if P, Q
If A then B = A→B = B if A <- Special case
Note they are swapped around if you only use ‘if’
Only if P, Q can be re-written as Q only if P which translates to Q→P
Only false when the 1st one (left of the → symbol) is true and the other one
is false
↔ Bi-condition P if and only if Q
ᴧ Conjunction (AND) and
but
however
v Disjunction (OR) or
either P or Q (¬ v)
Neither P nor Q
Means ¬P ᴧ ¬Q which can be simplified to ¬(P v Q)
,‘UNLESS’ example:
Unless you apply the brakes, you will crash
So if you NOT crash then it means you applied the brakes.
Means:
If NOT crashed, then braked.
If NOT braked, then Crashed.
Say we let Q be ‘applied the breaks’ and P be ‘you crash’
Then
Unless Q, then P
If NOT P, then Q
If NOT Q, then P
Sequent structure:
How to show if a sequent is valid or not valid:
A valuation of a formula is an assignment of each propositional atom to a truth table.
Identify the premises and the conclusion
Construct a truth table showing the truth values of the premises and the
conclusion
Look for all the rows where the premises are all true - we call such rows
critical rows. If the conclusion is false in a critical row, then the argument
, is invalid. Otherwise, the argument is valid (since the conclusion is
always true when the premises are true).
e.g.
HORN formula steps are:
1. Mark all T’s true if it occurs in the list
2. If everything on the left of the → is marked then mark the right as well
and also mark all instances of what was on the right and then go to step
2 again. Otherwise go to 3.
3. If contradiction is marked then Horn formula is unsatisfiable. Otherwise
go to 4.
4. Print out Horn formula is satisfiable and stop.
e.g.
,Step 1:
Step 2:
Step 2:
Step 2:
Step 3:
Contradiction is marked, thus Horn formula is not satisfiable.
Terms and WFF (Well formed formulas):
Variables, constants and functions are terms.
Well formed formulas (WFF)
To be well formed
, statements inside the brackets needs to be a term (variables, constants
or functions)
variables can’t stand alone without a capital letter/predicate. E.g. y
instead of P(y)
Not all variables need to be bound by a quantifier, i.e. a well formed
formula can have free variables.
Can’t use constant with quantifiers
WFF must have a predicate in them to be a WFF.
e.g.
Note you also have to take into account the information given like Q, S and P are
predicates with 2 variables. If they give those predicates with one argument then it is not
well formed.
Answers:
i) Not a WFF, because a quantifier can’t be inside the brackets of a predicate.
ii) Not a WFF, because a predicate can’t be inside another predicated brackets.
iii) It is a WFF.
iv) Not a WFF, because you can’t have quantifiers with constants.
v) Not a WFF (You are not allowed to have variable without predicate)
,Natural deduction
Rules:
Disjunction elimination
We have 2 sub proofs
Disjunction Introduction
If P is present then you can deduce that
Universal Quantifier Elimination:
Example:
, - WE assume variable inside block.
- Anywhere in this block we allowed to eliminate with the variables
becoming the variable chosen.
WORDING: If it is true for any variable then it must be true for a certain
variable.
Universal quantifier introduction:
Example:
- Introduce a variable
- Then if we find a WFF for that variable then we can introduce for
that WFF.
- Note the introduction happens outside the block where you introduced
the variable.
,We say for any arbiter variable chosen and we find that a WFF is true, then
WFF must be true for all variables
Existential quantifier introduction:
Example:
- If you have WFF with a variable inside the block then you can introduce
inside the block for that WFF.
- It can be introduced outside the block as well
Here we saying that if an variable exist for WFF then it is true for some (∃)
variable.
Existential quantifier elimination
This is the longest one.
Example:
, Note:
- You make an assumption of premise (or statement) that you want to
remove by replacing variable with arbitrary variable. Black arrow in picture
- Then from the assumption you get to any WFF. Blue line in picture
Then you allowed to introduce that WFF using elimination rule. Red line in
picture.
Example showing proof by contradiction and also how to do negation
elimination. i.e. contradiction intro.
