Logic and Truth Tables
Truth Tables
Negation (¬P)
This operation inverts the truth value of a proposition.
For proposition P:
When P is true (T), ¬P is false (F).
When P is false (F), ¬P is true (T).
Conjunction (P ∧ Q)
This operation is true only when both propositions are true.
The truth table is as follows:
P Q | P ∧ Q
T T | T
T F | F
F T | F
F F | F
Example: For statements "It is raining" and "It is cold", both must be true for the conjunction to be true.
Disjunction (P ∨ Q)
This operation is true if at least one of the propositions is true.
The truth table is:
P Q | P ∨ Q
T T | T
T F | T
F T | T
F F | F
Example: If it rains or snows, as long as one occurs, the disjunction is true.
Exclusive Or (P ⊕ Q)
This operation expresses that exactly one of the propositions must be true.
The truth table is:
P Q | P ⊕ Q
T T | F
T F | T
F T | T
F F | F
Example: In a scenario where a light can be on or off, but not both at the same time, exclusive or applies.
Conditional (P → Q)
This operation states that if P is true, then Q must also be true; it is only false when P is true and Q is false.
The truth table is:
P Q | P → Q
T T | T
T F | F
F T | T
F F | T
Example: If it rains (P), then the ground is wet (Q); if it rains but the ground is not wet, the implication fails.
Biconditional (P ↔ Q)
This operation is true if both propositions have the same truth value and is false if they differ.
The truth table is:
P Q | P ↔ Q
T T | T
T F | F
F T | F
F F | T
Example: The statement "You can go out if and only if you finish your homework" is only true if both propositions are either true or false together.
Logical Equivalences
Identity laws:
These laws affirm that a proposition maintained with a true or false value remains equal to itself.P ∧ T = P
P ∨ F = P
Domination laws:
These laws establish that the presence of a definite true or false value dominates the logical outcome.P ∨ T = T
P ∧ F = F
Idempotent laws:
These laws illustrate that repeating a proposition combined with itself retains the same truth value.P ∨ P = P
P ∧ P = P
Double negation law:
This law indicates that removing two negations reverts the proposition back to its original truth value.¬(¬P) = P
Commutative laws:
These laws show that the order of propositions in disjunction and conjunction does not affect the outcome.P ∨ Q = Q ∨ P
P ∧ Q = Q ∧ P
De Morgan's laws:
These laws express how negation interacts with conjunction and disjunction, essentially flipping the operators while maintaining the negation on the propositions.¬(P ∨ Q) = ¬P ∧ ¬Q
¬(P ∧ Q) = ¬P ∨ ¬Q
Quantifiers
Universal Quantifier (∀x P(x)):
This quantifier asserts that a property P holds for every element in the domain x.
True if P(x) holds for all values of x.
False if there exists at least one x for which P(x) is false.
Existential Quantifier (∃x P(x)):
This quantifier states that there is at least one element in the domain for which the property P holds true.
True if there is at least one x such that P(x) is true.
False if P(x) is true for every x (meaning there are no instances where P(x) is true).
Rules of Inference
Tautology:
An inference that is universally valid; it holds true in every possible interpretation.
Example: The statement "P or not P" is always true.
Modus Ponens:
A form of reasoning stating that given a conditional statement P → Q, if P is established as true, then Q must also be true.
Modus Tollens:
This rule states that if we know P → Q is true and Q is false, then P must also be false (¬P).
Hypothetical Syllogism:
This logical rule asserts that if P implies Q and Q implies R, then it can be inferred that P implies R.
Universal Instantiation:
This allows one to infer from a universally quantified statement that it holds for a specific instance (P(c) for some arbitrary c).
Existential Generalization:
This rule enables the inference that if P(c) is established for a specific case, there exists an x for which