# A proposition is any meaningful statement that is either true or false, but not both. We will use lowercase letters, such as p, q, r, · · · , to represent propositions. We will also use the notation
p : 1 + 1 = 3
# Statements that are not propositions include questions and commands.
# Compound propositions or propositional functions can be obtained from old ones by using symbolic connectives. The propositions that form a propositional function are called propositional variables. Let p and q be propositions. The conjunction of p and q, denoted by p ∧ q (read “p wedge q”), is the proposition: p and q. The disjunction of p and q, denoted by p ∨ q (read “p vee q”), is the proposition: p or q. the negation of p. The negation of p, denoted ∼ p, is the proposition not p.
Example:
Consider the following propositions
p : It is Friday
q : It is raining.
Construct the propositions p ∧ q and p ∨ q.
# A compound proposition is called a tautology if it is always true, regardless of the truth values of the propositional variables which comprise it.
# A compound proposition that has the value F for all possible values of the propositions in it is called a contradiction.
# Two propositions are equivalent if they have exactly the same truth values under all circumstances. We write p ≡ q.
Conditional and Biconditional Propositions:
Conditional:
Let p and q be propositions. The conditional proposition p → q is the proposition that is false only when p is true and q is false; otherwise it is true.
p is called the hypothesis and
q is called the conclusion.
The connective → is called the conditional connective.
implication p → q
# p → q ≡ (∼ p) ∨ q.
# p → q also reads:
(a) if p then q.
(b) p implies q.
(c) p is a sufficient condition for q.
(d) q is a necessary condition for p.
(e) p only if q.
# The converse of p → q is the proposition q → p.
# The opposite or inverse of p → q is the proposition ∼ p →∼ q.
# The contrapositive of p → q is the proposition ∼ q →∼ p. ( converse + opposite )
Biconditional:
The biconditional proposition of p and q, denoted by p ↔ q, is the propositional function that is true when both p and q have the same truth values and false if p and q have opposite truth values.
Also reads, “p if and only if q” or “p is a necessary and sufficient condition for q.”
# equivalent to the conjunction of the conditional propositions p → q and q → p
# In propositional functions, the order of operations for the five logical connectives is as follows:
1. ~
2. ∧, ∨ in any order.
3. →, ↔ in any order.
Related Propositions: Inference Logic
An argument is a set of two or more propositions related to each other in such a way that all but one of them, the premises, are supposed to provide support for the remaining one, the conclusion. The transition from premises to conclusion is the inference upon which the argument relies.
Now, suppose that the premises of an argument are all true. Then the
conclusion may be either true or false. When the conclusion is true then the
argument is said to be valid. When the conclusion is false then the argument
is said to be invalid.
To test an argument for validity one proceeds as follows:
(1) Identify the premises and the conclusion of the argument.
(2) Construct a truth table including the premises and the conclusion.
(3) Find rows in which all premises are true.
(4) In each row of Step (3), if the conclusion is true then the argument is
valid; otherwise the argument is invalid.
Some basic rules of inference:
1. Modus Ponens or the method of affirmative:
p → q
p
.'. q
How to justify using truth table:
p q p → q
T T T
T F F
F T T
F F T
2. Modus Tollens or the method of denial:
p → q
~ q
.'. ~p
3. Disjunctive Addition:
p
.'. p ∨ q
4. Conjunctive addition:
p, q
.'. p ∧ q
5. Conjunctive simplification:
p ∧ q
.'. p
6. Disjunctive syllogism
p ∨ q
~ q
.. p
7. Hypothetical syllogism
p → q
q → r
.. p → r
8. Rule of contradiction
if c is a contradiction then the following argument is valid for any
p.
∼ p → c
.. p
Predicates and Quantifiers:
A predicate is an expression involving one or more variables defined on some domain, called the domain of discourse. Substitution of a particular value for the variable(s) produces a proposition which is either true or false. For instance, P (n) : n is prime is a predicate on the set of natural numbers1 N. Observe that P (1) is false, P (2) is true. In the expression P (x), x is called a free variable. As x varies the truth value of P (x) varies as well. The set of true values of a predicate P (x) is called the truth set and will be denoted by TP .
If P (x) and Q(x) are two predicates with a common domain D then the notation P (x) ⇒ Q(x) means that every element in the truth set of P (x) is also an
element in the truth set of Q(x). Same logical manipulations that were used
with propositions can be used with predicates. For example, P (x) ⇒ Q(x)
is the same as ∼ P (x) ∨ Q(x).
Example 5.2
Consider the two predicates P (x) : x is a factor of 4 and Q(x) : x is a factor
of 8. Show that P (x) ⇒ Q(x). Finding the truth set of each predicate we have: TP = {1, 2, 4} and TQ =
{1, 2, 4, 8}. Since every number appearing in TP also appears in TQ we have P (x) ⇒ Q(x)
If two predicates P (x) and Q(x) with a common domain D are such that
TP = TQ then we use the notation P (x) ⇔ Q(x).
Quantifiers:
A quantifier turns a predicate into a proposition without assigning specific values for the variable. There are primarily two quantifiers: Universal
quantifier and existential quantifier.
Universal:
The universal quantification of a predicate P (x) is the proposition ∀x ∈ D, P (x) is true, where the symbol ∀ is the universal quantifier. For example, if k is a non-negative integer, then the predicate P (k) : 2k is even is true for all k ∈ W. Using the universal quantifier ∀, we can write, ∀k ∈ W, (2k is even). The proposition ∀x ∈ D, P (x) is false if P (x) is false for at least one value of x. In this case, x is called a counterexample.
existential:
The existential quantification of the predicate P (x) is the proposition
∃x ∈ D, P (x) that is true if there is at least one value of x ∈ D where
P (x) is true; otherwise it is false. The symbol 'Ulta(E)' is called the existential
quantifier.
Nested Quantifiers
Next, we discuss predicates that contain multiple quantifiers. A typical example is the definition of a limit. We say that L = limx→a f(x) if and only if
∀ > 0, ∃ a positive number δ such that if |x − a| ≤ δ then |f(x) − L| < .
0 comments:
Post a Comment