Logic and Propositions Overview

Proposition

• A sentence that is either true or false, but not both simultaneously.
• Represented with letters like P, Q, and R.
• If true, assigned value 1 (or T).
• If false, assigned value 0 (or F).

Truth Table

• Shows different truth values for propositions.

Predicate

• Logical formula dependent on a free variable.

Negation

• "Not P" or "¬P"
• True if P is false and false if P is true.

Conjunction

• "P and Q" or "P ∧ Q"
• True if both P and Q are true, false otherwise.

Disjunction

• "P or Q" or "P ∨ Q"
• False if both P and Q are false, true otherwise.

Implication

• "If P then Q" or "P ⇒ Q"
• False only when P is true and Q is false, true otherwise.
• P is sufficient for Q.
• Q is necessary for P.

Equivalence

• "P if and only if Q" or "P ⇔ Q"
• True if both P and Q have the same truth value, false otherwise.
• P is both necessary and sufficient for Q.

Direct Proof

• To show "P ⇒ Q" is true, assume P is true and show that Q is true.

Proof by Cases

• To show a statement P(x) is true for all x in a set E, show P(x) is true for all x in a subset A of E and then for all x in A.

Proof by Contrapositive

• To show "P ⇒ Q" is true, show its contrapositive "¬Q ⇒ ¬P" is true.

Proof by Contradiction

• To show "P ⇒ Q", assume P is true and Q is false (¬Q is true) and arrive at a contradiction.
• This proves that if P is true, then Q must also be true.

Proof by Counter Example

• To disprove a statement "∀x ∈ E: P(x)", find an element x in E such that P(x) is false.

Proof by Induction

• To show P(n) is true for all natural numbers n, do the following:
  • Prove that P(n₀) is true (n₀ is the initial value of n).
  • Assume P(n) is true for all n and prove that P(n + 1) is true.

Set

• A collection of distinct objects called elements.
• Elements are denoted by x ∈ E, meaning x is an element of set E.

Empty Set

• Denoted by Ø, contains no elements.

Cardinality

• Number of elements in a set, denoted card(E).

Inclusion (Subset)

• F ⊂ E means every element of F is an element of E.
• F is a subset of E.

Equality of Sets

• E = F if and only if both E ⊆ F and F ⊆ E are true.

Intersection

• A ∩ B = {x ∈ E/ x ∈ A and x ∈ B}

Union

• A ∪ B = {x ∈ E / x ∈ A or x ∈ B}

Complement

• Ā = {x ∈ E : x ∉ A}

Difference

• A − B = {x ∈ E/ x ∈ A and x ∉ B}

Symmetric Difference

• A∆B = (A - B) ∪ (B - A) = {x ∈ E/ (x ∈ A and x ∉ B) or (x ∈ B and x ∉ A)}.

Power Set

• Set of all subsets of a set E, denoted by P(E).
• If card(E) = n, then card(P(E)) = 2^n.

Partition

• (E1, E2, ..., En) form a partition of E if:
  • Each set is non-empty.
  • They are pairwise disjoint.
  • Their union is equal to E.

This quiz covers the fundamental concepts of logic, including propositions, truth tables, and logical operators such as conjunction, disjunction, negation, and implication. Test your understanding of these concepts and their interrelations in logical reasoning.