maths.free › Discrete Math & Logic › Truth tables

Truth tables

And, or, not, implies — and tautologies.

A truth table lists every combination of truth values for the variables and the value of the whole statement in each case. A statement true in every row is a tautology; one false in every row is a contradiction. Try p implies q and not p or q and compare.

Eżempju maħdum: truth table of p and q

Discrete-Math · Propositional-Logic

Truth table of p and q

Pass b'pass

  1. p \wedge q

    2 variable(s) → 4 rows. Fill in every combination.

  2. \

    Contingent: true for some inputs, false for others.

Jiżvelaw it-tweġiba
p \wedge q

Symbols used here

\neg,\ \wedge,\ \vee,\ \Rightarrow,\ \Leftrightarrow
not, and, or, implies, iff
Logical connectives.
n!
factorial
n × (n−1) × … × 1; the number of orderings of n things. 0! = 1.
\binom{n}{k}
binomial coefficient, "n choose k"
Number of k-element subsets of n things: n!/(k!(n−k)!).
\sum_{k=1}^{n} a_k
summation
Add a_k for k = 1 up to n.
x \in A,\ A \subseteq B
element of, subset
x belongs to A; every element of A is in B.
A \cup B,\ A \cap B,\ A \setminus B
union, intersection, difference
In either; in both; in A but not B.
\emptyset,\ |A|
empty set, cardinality
The set with no elements; the number of elements of A.
\forall,\ \exists
for all, there exists
Quantifiers: every x; at least one x.
\blacksquare\ \text{or}\ \square
end of proof (halmos)
Marks the point where the statement has been established.
a \equiv b \pmod n
congruent modulo n
n divides a − b; a and b have the same remainder.
O(n^2),\ \Theta,\ \Omega
big-O notation
Grows no faster than n² (up to a constant), for large n.
a \bmod n
remainder
What is left after dividing a by n.

How to: Truth tables

  1. 2 variable(s) → 4 rows. Fill in every combination.
  2. Contingent: true for some inputs, false for others.

Questions people ask

What makes mathematics "discrete"?

It deals with separate, countable objects — integers, graphs, statements — rather than continuous quantities. No limits, no infinitesimals; instead induction, counting and logic.

How does a proof by induction work?

Show the statement for the first case, then show that whenever it holds for n it holds for n + 1. Like dominoes: the first falls, and each knocks over the next.

Ipprova tiegħek stess

Aktar fil Discrete Math & Logic

Sums and inductionProof by inductionAlgorithms and growth of functions