This summary contains in depth concepts, explanations and examples which will not only allow you to reduce the amount of time you have to study, but will also assist you with getting a distinction for this module. The following concepts are covered in this summary: Predicate Logic, Truth Tables, Co...
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.
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller francoissmit. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $4.50. You're not tied to anything after your purchase.
