6 Q Theory of Computer Science
(a) (-, P /\ Q) ¢::} R
(b) (Q ::::} R) /\ (R ::::} Q)
(c) -, (Q v R)
(d) R ::::} -, P /\ Q
Solution
(a) I will go to a movie if and only if it is not raining and I have the
time.
(b) I will go to a movie if and only if I have the time.
(c) It is not the case that I have the time or I will go to a movie.
(d) I will go to a movie, only if it is not raining or I have the time.
1.1 .2 WELL-FORMED FORMULAS
Consider the propositions P /\ Q and Q /\ P. The truth tables of these two
propositions are identical irrespective of any proposition in place of P and any
proposition in place of Q. SO we can develop the concept of a propositional
variable (corresponding to propositions) and well-formed formulas
(corresponding to propositions involving connectives).
Definition 1.1 A propositional variable is a symbol representing any
proposition. We note that usually a real variable is represented by the symbol
x. This means that x is not a real number but can take a real value. Similarly,
a propositional variable is not a proposition but can be replaced by a
proposition.
Usually a mathematical object can be defined in terms of the property/
condition satisfied by the mathematical object. Another way of defining a
mathematical object is by recursion. Initially some objects are declared to
follow the definition. The process by which more objects can be constructed
is specified. This way of defining a mathematical object is called a recursive
definition. This corresponds to a function calling itself in a programming
language.
The factorial n! can be defined as n(n - 1) ... 2.1. The recursive
definition of n! is as follows:
O! = 1, n! = n(n - I)!
Definition 1.2 A well-formed formula (wff) is defined recursively as
follows:
(i) If P is a propositional variable, then it is a wff.
(ii) If ex is a wff, then -, ex is a wff.
(iii) If ex and f3 are well-formed formulas, then (ex v /3), (ex /\ /3), (ex::::} /3),
and (ex ¢::} /3) are well-formed formulas.
(i v) A string of symbols is a wff if and only if it is obtained by a finite
number of applications of (i)-(iii).
http://engineeringbooks.net
(a) (-, P /\ Q) ¢::} R
(b) (Q ::::} R) /\ (R ::::} Q)
(c) -, (Q v R)
(d) R ::::} -, P /\ Q
Solution
(a) I will go to a movie if and only if it is not raining and I have the
time.
(b) I will go to a movie if and only if I have the time.
(c) It is not the case that I have the time or I will go to a movie.
(d) I will go to a movie, only if it is not raining or I have the time.
1.1 .2 WELL-FORMED FORMULAS
Consider the propositions P /\ Q and Q /\ P. The truth tables of these two
propositions are identical irrespective of any proposition in place of P and any
proposition in place of Q. SO we can develop the concept of a propositional
variable (corresponding to propositions) and well-formed formulas
(corresponding to propositions involving connectives).
Definition 1.1 A propositional variable is a symbol representing any
proposition. We note that usually a real variable is represented by the symbol
x. This means that x is not a real number but can take a real value. Similarly,
a propositional variable is not a proposition but can be replaced by a
proposition.
Usually a mathematical object can be defined in terms of the property/
condition satisfied by the mathematical object. Another way of defining a
mathematical object is by recursion. Initially some objects are declared to
follow the definition. The process by which more objects can be constructed
is specified. This way of defining a mathematical object is called a recursive
definition. This corresponds to a function calling itself in a programming
language.
The factorial n! can be defined as n(n - 1) ... 2.1. The recursive
definition of n! is as follows:
O! = 1, n! = n(n - I)!
Definition 1.2 A well-formed formula (wff) is defined recursively as
follows:
(i) If P is a propositional variable, then it is a wff.
(ii) If ex is a wff, then -, ex is a wff.
(iii) If ex and f3 are well-formed formulas, then (ex v /3), (ex /\ /3), (ex::::} /3),
and (ex ¢::} /3) are well-formed formulas.
(i v) A string of symbols is a wff if and only if it is obtained by a finite
number of applications of (i)-(iii).
http://engineeringbooks.net