Examples in Logic
Principles of Computer Engineering Homework 4
Peter Asenov Ruevski
The predicate calculus has a number of theorems and axioms for proving logical statements. Here are the main symbols used in predicate calculus:
P(x) proposition a logical statement in the condition x.
x any condition in the set of possible conditions.
c a particular condition in the set of possible conditions.
" "For every"
Ù Conjunction (logical and)
When proving a logical statement we start with some true statements and based on them using equivalencies we write new statements. The goal of this homework is to discuss some of the basic equivalencies (productions) used, to consider them in "real life situations" and to comment on their validity in this case.
The statement above is read: "If P is true and P implies Q then Q is also true".
The statement above is read: "If for every condition x, P(x) is true then P(c) is true (i.e. P is true for a particular condition c)".
Universal instantiation should be correct, because from a set of conditions for which the statement is correct we choose a particular one.
" x, P(x)
The statement above is read: "If P(x) is true, then for every x, P(x) is true".
The problem with giving an example is that P(x) must be "general truth". To find a "general truth" we have to restrict the space of conditions because (I think so) nothing is true for any conditions.
I think that the Universal Generalisation is the way we create axioms (even the name supports this) or define new terms (words). There is no way to prove that it is true. You just accept it (or believe it) and use it. For example I can make this statement:
Is it better than the original? Can you prove it? No. It is just a definition for byte you can define it any way you want.
The statement above is read: "If there exists an x for which P(x) is true then P(c) is true (i.e. there is a particular condition c for which P is true)".
Existential Instantiation is correct in my opinion.
$ x, P(x)
The statement above is read: "If P(c) is true (for a particular condition c) then there exists (at least one) condition x for which P is true". Existential generalisation is just the opposite of existential instantiation.
From the previous examples the second is always correct, but it seems like the first one is not necessarily true. The problem with the first statement is that it seemingly is not taking into account the fact that an engine can be broken. But it is taken into account because if the engine runs on gas, then it is not broken. In fact it is illegal to go "out" out the set you are working with. The second one has the same "problem".
In my opinion the Existential Generalisation is valid for all cases.
All the logical models of reasoning are axioms therefore they can not be proved. An axiom can only be proven incorrect if a contra-example is found. But unlike axioms in physics, which predict real measurable events and therefore can be verified (and proven incorrect like the Newtonian theory of gravity. The axioms in logic deal oly with language constructs. So for every properly constructed input they will produce the expected output (even if the construct has nothing to do with "reality", like in the "byte is snow" example). The only way wrong results can come out of logical reasoning is if we exceed the set we are working with i.e. implicitly accept something that is not true or use facts for which no propositions are defined.