Principles of Computer Engineering – Homework 4

By
Peter Asenov Ruevski
E-mail: Ruevs@drexel.edu

1. Introduction

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"

$ – "Exists"

® – Implication

Ù – Conjunction (logical and)

• – disjunction (logical or)

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.

1. Logical models of reasoning
1. Modus Ponens
1. Definition and explanation

P
P® Q
---------
Q

The statement above is read: "If P is true and P implies Q then Q is also true".

2. Examples

• If there is fire and fire implies smoke, then there is smoke.
  P fire exists
  P® Q fire® smoke
  Q smoke
• If

1. Statement of correctness

1. Universal Instantiation
1. Definition and explanation

" x, P(x)
-----------
P(c)

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)".

2. Examples

• If a bird can fly in any weather, then it can fly when it rains
  " x, P(x) For every weather – bird can fly
  P(c) bird can fly when it rains
• If there is a key for every lock, then there is a key for a particular lock.
  " x, P(x) For every lock – exists a key
  P(c) key exists for "this" lock.

1. Statement of correctness

Universal instantiation should be correct, because from a set of conditions for which the statement is correct we choose a particular one.

1. Universal Generalisation
1. Definition and explanation

P(x)
-----------

" x, P(x)

The statement above is read: "If P(x) is true, then for every x, P(x) is true".

2. Examples

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.

• If "byte is 8bits of ordered information", then any 8 ordered bits of information are a byte.
  P(x) byte – 8 bits of ordered information
  " x, P(x) any 8 ordered bits of information – byte.
• If "a single line passes through two points", then a single line passes through any two points.
  P(x) single line through two points
  " x, P(x) through any two points – single line

1. Statement of correctness

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:

• If "byte carries 4bits of information", then any byte carries 4 bits of information.

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.

• If "byte is the dirty snow that your neighbour put on your carpet when he came to ask for a cup of sugar", then any dirty snow put on your carpet by your neighbour coming to ask for a cup of sugar is byte.

1. Existential Instantiation
1. Definition and explanation

$ x, P(x)
----------
P(c)

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)".

2. Examples

• If a valid password exists for some UNIX system, then you can access that UNIX system with a particular password.
  " x, P(x) exists a password – to log in
  P(c) you can log in with some particular password.
• If a proof for the Pythagorean theorem exists, then the Pythagorean theorem can be proved.
  " x, P(x) exists a proof for Pythagorean theorem
  P(c) a particular proof can be used to do it.
• If a path if a path through a labyrinth exists, then the labyrinth can be traversed through a particular path.
  " x, P(x) a path in the labyrinth exists
  P(c) using a particular path the labyrinth can be traversed.

1. Statement of correctness

Existential Instantiation is correct in my opinion.

1. Existential Generalisation
1. Definition and explanation

P(c)
----------
$ 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.

2. Examples

• If an engine runs on gas, then there exists a fuel on which the engine runs. (if it’s not broken)
  P(c) engine – runs on gas (set – fuels)
  $ x, P(x) exists a fuel to run engine
• If you can access a UNIX system with a particular password, then a valid password exists for that UNIX machine.
  P(c) can access UNIX machine
  $ x, P(x) exists a password for it (unless you hack in)
• If water boils over 100° C then there exists a temperature over which water boils.

1. Statement of correctness

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.

1. Conclusion

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.