The disjunction of statements P and Q is expressed as "P or Q" and is denoted by P v Q.
The disjunction P v Q is true if at least one of P or Q is true.
It is false only when both P and Q are false.
If it is not possible for both statements to be true (e.g., "n is even or n is odd"), this scenario is referred to as exclusive or (XOR).
The conjunction of the statements P and Q is expressed as "P and Q" and is denoted by P ^ Q.
The conjunction P ^ Q is true if both P and Q are true.
It is false if at least one of P and Q is false.
Let:
P: 3 is odd
Q: 57 is prime
Here, P v Q is true because P is true.
However, P ^ Q is false because Q is false.
For statements P and Q, the implication (or conditional) is the statement "If P, then Q" or "P implies Q" and is denoted by P β Q.
P is the hypothesis or premise, while Q is the conclusion.
The implication P β Q is false only when P is true and Q is false.
Let:
P: 3 is odd
Q: 57 is prime
The implication P β Q: If 3 is odd, then 57 is prime is false, as P is true but Q is false.
Conversely, Q β P: If 57 is prime, then 3 is odd is a true statement because P is true.
The implication P β Q can also be expressed in other ways:
"Q if P"
"P only if Q"
"P is sufficient for Q"
"Q is necessary for P"
For statements P and Q, construct a truth table for (P β Q) β (~P).
P | Q | P β Q | ~P | (P β Q) β (~P) |
---|---|---|---|---|
T | T | T | F | F |
T | F | F | F | T |
F | T | T | T | T |
F | F | T | T | T |
Consider the open sentences P(x): x=-3 and Q(x): |x|=3.
We can form other open sentences:
~P(x): x β -3
P(x) v Q(x): x=-3 or |x|=3
P(x) ^ Q(x): x=-3 and |x|=3
P(x) β Q(x): If x=-3, then |x|=3.
For x = -3,
~P(-3) is false.
P(-3) v Q(-3) and P(-3) ^ Q(-3) are both true.
However, P(3) v Q(3) is true while P(3) ^ Q(3) is false since P(3) is false.
The biconditional for statements P and Q combines P β Q and Q β P.
It is denoted as P β Q and means that both statements are true simultaneously.
The biconditional P β Q is expressed as:
"P if and only if Q"
"P is equivalent to Q"
This statement is only true when P and Q have the same truth value.
Let:
P: 3 is odd
Q: 57 is prime
The biconditional "3 is odd if and only if 57 is prime" is false since its parts have differing truth values.
The symbols ~, v, ^, β, and β are called logical connectives.
A compound statement is formed by combining component statements using at least one logical connective.
A compound statement is a tautology if it is true for all possible combinations of truth values of its components.
The statement P v (~P) is a tautology:
P | ~P | P v (~P) |
---|---|---|
T | F | T |
F | T | T |
Conversely, a compou...
Two compound statements R and S are logically equivalent if they have the same truth values for all possible combinations of truth values of their components. This is denoted by R = S.
(P ^ Q) = (Q ^ P)
(P β Q) = (~P v Q)
Commutative Laws:
P v Q = Q v P
P ^ Q = Q ^ P
Associative Laws:
P v (Q v R) = (P v Q) v R
P ^ (Q ^ R) = (P ^ Q) ^ R
Adding quantifiers to open sentences results in quantified statements.
The universal quantifier (for all) is denoted by β:
For all x in S, P(x)
The existential quantifier (there exists) is denoted by β:
There exists x in S such that P(x).
The truth of a quantified statement depends on the truth of the underlying open sentence for respective components.
A direct proof is a method of proving a statement by straightforward logical deductions from accepted truths or previously established statements. In a direct proof, the conclusion is reached by a chain of logical implications from the hypothesis.
To prove that if n is an even integer, then n^2 is even:
Assume n is even (there exists an integer k such that n = 2k).
Therefore, n^2 = (2k)^2 = 4k^2 = 2(2k^2), which is also even.
A trivial proof occurs when the conclusion follows immediately from the hypothesis. In these cases, the statement is straightforward and requires minimal justification.
To prove that if P is true, then Q is true when Q is inherently true (regardless of P).
If it rains, then 2 + 2 = 4. Since the conclusion is always true, the proof is considered trivial.
A vacuous proof is a special type of proof that occurs when the hypothesis of an implication is false. In this case, the implication is considered true regardless of the truth value of the conclusion.
To prove that if x > 5, then x^2 < 0:
Here, the hypothesis x > 5 is false because x cannot be simultaneously greater than 5 and have a square less than 0. Therefore, the implication is vacuously true.