Mathematical Logic and Discrete Mathematics Flashcards

A collection of vocabulary terms exploring the foundations of mathematical logic, including propositions, connectives, conditional forms, truth tables, logic gates, and quantifiers.

Proposition

A declarative sentence that is either true or false, but not both.

Propositional Calculus

The study of the logical relationships between statements called propositions, being interpretable as meaningful assertions in real-life contexts.

Propositional Variables

Letters such as $x, y, z, p, q, r$ used in logic to denote variables that can be replaced by statements.

Compound Statements

Statements or propositional variables that are combined by logical connectives.

Connectives

Logical operators such as "not", "and", "or", "if…then…", and "if and only if" used to form new propositions from two or more existing propositions.

Negation

Definition: Let $p$ be a proposition. The statement "It is not the case that P" is another proposition denoted by $\overline{P}$.

Conjunction

The proposition "P and Q," denoted by $P \wedge Q$, which is true when both $P$ and $Q$ are true and is false otherwise.

Disjunction

The proposition "P or Q," denoted by $P \vee Q$, which is false when both $P$ and $Q$ are false and true otherwise.

Antecedent

The statement $P$ in an implication $P \rightarrow Q$, also referred to as the premise or hypothesis.

Consequent

The statement $Q$ in an implication $P \rightarrow Q$, also referred to as the conclusion.

Bi-conditional

The proposition "$P \leftrightarrow Q$" which is true when $P$ and $Q$ have the same truth values and false otherwise.

Exclusive Or

The proposition denoted by $P \oplus Q$ that is true when exactly one of $P$ and $Q$ is true and is false otherwise.

Converse

The form of a conditional statement where the hypothesis and conclusion are interchanged: $Q \rightarrow P$.

Inverse

The form of a conditional statement where both the hypothesis and the conclusion are negated: $\overline{P} \rightarrow \overline{Q}$.

Contrapositive

The form of a conditional statement created by switching the hypothesis and conclusion and negating both: $\overline{Q} \rightarrow \overline{P}$.

Truth Table

A diagram in rows and columns showing how the truth or falsity of a proposition varies with 그 component parts.

Logic Gate

An elementary building block of a digital circuit where terminals are in one of two binary conditions: low ($0$) or high ($1$).

NAND Gate

A logic gate that operates as an AND gate followed by a NOT gate, where the output is false if both inputs are true.

NOR Gate

A logic gate that is a combination of an OR gate followed by an inverter, where the output is true if both inputs are false.

Tautology

A class of compound propositions that are always TRUE for all possible combinations of $P, Q$, and $R$.

Contradiction

A compound proposition that is always false, also known as an absurdity.

Contingent

A compound proposition that is neither a tautology nor a contradiction.

Logical Equivalence

Two statements $P$ and $Q$ where the notation $P \equiv Q$ denotes that the compound proposition $P \leftrightarrow Q$ is a tautology.

Proof

An argument from hypotheses (assumptions) to a conclusion where each step follows the laws of logic.

Predicate

A sentence that contains a finite number of variables and becomes a statement when specific values are substituted for those variables.

Universal Quantifier

The notation $\forall x$ which indicates that a predicate $P(x)$ is true for all values of $x$ in the universe of discourse.

Existential Quantifier

The notation $\exists x$ which indicates that there exists at least one $x$ in the universe of discourse such that the predicate $P(x)$ is true.

Nested Quantifiers

A condition where one quantifier is located within the scope of another quantifier.