Compound proposition

A compound proposition is a proposition formed by joining individual propositions with logical connectives. The truth value of a compound proposition depends on the truth values of the propositions that comprise it.

Contents

Truth table

Like regular propositions, compound propositions can only either be true or false. However, because the truth value of a compound proposition depends on the truth values of the propositions that comprise it, there are many ways a compound proposition could evaluate as true or false. To solve this issue, we draw truth tables. A truth table shows the corresponding truth value of a compound proposition for every possible combination of truth values.

If a compound proposition is made up of \(n\) propositions, its truth table will need \(2^n\) rows of truth values.

When a compound proposition is really complicated, it can help to break it up into smaller compound propositions and evaluate them in the truth table separately. That way, you won't be overwhelmed when you try to evaluate the full compound proposition.

Notice that the individual propositions are on the left while the compound propositions are on the right. As a rule, propositions should be displayed in order of increasing complexity.

To make sure you get every possible combination of truth values, you'll need to alternate between true and false differently for each individual proposition. The rightmost individual proposition should have alternating T's and F's, while the second to the right should have alternating TT's and FF's, then TTTT's and FFFF's, and so on.

Logic & Proofs

Integer • Rational number • Inequality • Real number • Theorem • Proof • Statement • Proof by exhaustion • Universal generalization • Counterexample • Existence proof • Existential instantiation • Axiom • Logic • Truth • Proposition • Compound proposition • Logical operation • Logical equivalence • Tautology • Contradiction • Logic law • Predicate • Domain • Quantifier • Argument • Rule of inference • Logical proof • Direct proof • Proof by contrapositive • Irrational number • Proof by contradiction • Proof by cases • Summation • Disjunctive normal form

Set Theory

Set • Element • Empty set • Universal set • Subset • Power set • Cartesian product • String • Binary string • Empty string • Set operation • Set identity • Set proof

Functions

Function • Floor function • Ceiling function • Inverse function

Algorithms

Algorithm • Pseudocode • Command • Asymptotic notation • Time complexity • Atomic operation • Brute-force algorithm

Relations

Relation • Reflexive relation • Symmetric relation • Transitive relation • Relation composition • Equivalence relation • Equivalence class

Number Theory

Integer division • Linear combination • Division algorithm • Modular arithmetic • Prime factorization • Greatest common divisor • Least common multiple • Primality test • Factoring algorithm • Euclid's theorem • Prime number theorem • Euclidean algorithm

Induction

Proof by induction • Fibonacci sequence • Proof by strong induction • Well-ordering principle • Sequence • Factorial • Recursive definition

Combinatorics

Rule of product • Rule of sum • Bijection rule • Permutation • Combination • Complement rule • Experiment • Outcome • Sample space • Event • Probability • Probability distribution • Uniform distribution • Multiset • Sixfold way • Inclusion-exclusion principle • Pigeonhole principle

Graph Theory

Graph • Walk • Subgraph • Regular graph • Complete graph • Empty graph • Cycle graph • Hypercube graph • Bipartite graph • Component • Eulerian circuit • Eulerian trail • Hamiltonian cycle • Hamiltonian path • Tree • Huffman tree • Substring • Forest • Path graph • Star • Spanning tree • Weighted graph • Minimum spanning tree • Greedy algorithm • Prim's algorithm

Recursion

Recursion • Recursive algorithm • Correctness proof • Divide-and-conquer algorithm • Sorting algorithm • Merge sort