ICS 6B Sections 1.1-1.5

1.1: Propositions and logical operations

Proposition: A statement that is either true or false
- Does not include commands (Shut the door!) or questions (What time is it?)
- Propositions have a truth value, can be either: true, false, unknown, or a matter of opinion
A compound proposition is the combination of propositions using a logical operator
- ∧ represents “and”; p ∧ q is true if both p and q are true
  - AKA conjunction operator
  - Truth table:
- ∨ represents “or”; p ∨ q is true if either p or q are true
  - AKA disjunction operator
  - Truth Table:
- In English, “or” is typically used to represent “either/or”, or exclusive or (represented by ⊕), where both conditions cannot be true at the same time (She is eating or running)
  - Only difference is that T ⊕ T == F while T ∨ T == T
  - ∨ represents inclusive or where both conditions CAN be true at the same time
- ¬ represents negation, or NOT; ¬True == False and ¬False == True

Compound propositions can have more than one operation
- Order of operations w/o parantheses: ¬ (not), ∧ (and), ∨ (or)
- Good practice to use parantheses
- Truth tables will contain 2ⁿ rows for n variables(2 options for each variable)
- Rightmost variable is filled in with TFTF…, leftmost is filled in with TTFF…; T and F alternates based on 2^{column number} where rightmost column = 1
Example of a truth table with intermediate steps:

Conditional operations are represented with the symbol →
- p → q is read as “if p then q”
- Truth table:
- Think of it as a contract; if condition one is fulfilled, then the second condition HAS to be fulfilled, but if condition one is not fulfilled, then the second condition can either be fulfilled or not.
- Different ways to express conditional operations:
- p only if q is also p → q; most confusing one
Related conditional statements include the contrapositive, converse, and inverse
- The converse of p → q is q → p
- The contrapositive of p → q is ¬q → ¬p
- The inverse of p → q is ¬p → ¬q
Biconditional operations are represented with ↔
- p ↔ q stands for “p if and only if q” - AKA true if p == q and false if not
- If and only if can be represented with iff
Conditional and biconditional operations can be used in conjunction with other operations
- ∧, ∨, and ¬ takes precedence before → or ↔

A tautology is a compound proposition that is always true, while a contradiction is a compound proposition that is always false
- p ∨ ¬p is a tautology, while p ∧ ¬p is a contradiction
Logical equivalence means that two compound propositions always return the same value
- ≡ is used to denote logical equivalence
- If s ≡ r, then s ↔ r is a tautology, and s ≡ r if and only if r ≡ s
De Morgan’s Laws are laws that use logical equivalences to show how to distribute negation, or NOT, operations
- First version of the law: ¬(p ∨ q) ≡ (¬p ∧ ¬q) or !(p or q) == !p and !q
- Second version of the law: ¬(p ∧ q) ≡ (¬p ∨ ¬q) or !(p and q) == !p or !q

NOTE TO SELF: Challenge activity 1.4.1 is a great capstone activity for practice

You can substitute a proposition in for another one if both propositions are logically equivalent
- ex: Because p → q ≡ ¬p ∨ q, (p ∨ r) ∧ (¬p ∨ q) ≡ (p ∨ r) ∧ (p → q)
- Useful laws for logical equivalence:

NOTE TO SELF: Challenge activities 1.5.1-1.5.3 are great practice activities