Propositions
In logic, a proposition is a statement that evaluates true or false, such as “all cars are blue” or “4 + 4 = 8.” A phrase such as “go outside” is a command and not a proposition because it does not have a true or false value. Propositional statements can be denoted by variables, such as Q = "all cars are blue,"
or P = "4 + 4 = 8,"
which evaluate to Q = False
and P = True
.
Compound Propositions
Compound propositions are the result of combining multiple propositions. For example, K = Q and P
. That compound proposition evaluates to false because, as we’ve seen, Q is false. We can make K evaluate to true by changing the compound proposition to K = Q or P
. The condition here is that only one variable must evaluate true for K to be true because we are saying “or” instead of “and.”
Logic Operators
logical operators refer to operations that combine propositions, such as the “and” and “or” operators we’ve previously used. Below is a list of logical operators and their denotations in discrete mathematics.
The conjunction operation is denoted by ∧ and read as “and,” such as:
K = Q ∧ P
read as
K = Q and P
The disjunction operation reads as “or” and has two distinctions, the “exclusive or” and the “inclusive or.”
The “inclusive or” denoted by ∧ and reads as “or” dictates that a compound proposition is true if either statement is true.
Inclusive-or example:
K = True
P = False
N = True
R = K ∧ P ∧ N
R evaluates to True when either K, P, or N is true.
The “exclusive or” denoted by ⊕ and reads as “or” dictates that only one operation must evaluate true for the compound proposition to be true.
Exclusive-or example:
K = True
P = False
N = True
R = K ∧ P ∧ N
R evaluates to False when more than variables are true.
The negation operation, denoted by ¬ and read as “not,” reverses the value of a proposition. ¬Q is read as “not Q.”
Negation operation example:
P = True
T = False
Q = P ∧ T (Q evaluates to true because P is true)
Q = ¬P ∧ T (Q evaluates to false because both P and T are false)
The negation of ¬P reversed P’s value from True to False.
Order of Operation
The order of operation for compound propositions is (¬) negation first, (∧) conjunction second, and (∨) disjunction last.
- ¬ (not)
- ∧ (and)
- ∨ (or)
Similar to the order of operation in mathematics, everything in parenthesis is applied first except that the negation operation (¬) always takes precedence.
Order of operation examples
Example #1F ∨ T ∧ T
F ∨ (T ∧ T)
(Conjunction has precedence over disjunction)F ∨ (T)
(True and True evaluate to True)T
(False or True evaluate to True)
Example #2¬F ∨ T ∧ T
(¬F) ∨ T ∧ T
(Negation has precedence over conjunction and disjunction(¬F) ∨ (T ∧ T)
(Conjunction has precedence over disjunction)(¬F) ∨ T
(True and True evaluate to True)T ∨ T
(Negation of False evaluates to True)T
(True and True evaluate to True)