Discrete Mathematics Notes part 1

Flashcards covering key vocabulary and concepts in Discrete Mathematics related to Propositional Logic and Quantifiers.

Proposition

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

Truth Value

The value indicating whether a proposition is true or false.

Logical Operators

Symbols used to represent logical operations, such as conjunction, disjunction, and negation.

Conjunction (∧)

A logical operation that results in true if both operands are true.

Disjunction (∨)

A logical operation that results in true if at least one operand is true.

Negation (¬)

A logical operation that inverts the truth value of a proposition.

Implication (→)

A logical operation indicating that if one proposition is true, then another proposition is also true.

Equivalence (↔)

A logical statement that two propositions are equivalent; both are true or both are false.

Truth Table

A table used to determine the truth values of logical expressions based on all possible combinations of truth values of propositions.

Conjunctive Normal Form (CNF)

A way of structuring a logical formula where it is expressed as a conjunction of clauses, and each clause is a disjunction of literals.

Quantifier

A symbol used to indicate the scope of the variables in logical statements, such as universal (∀) or existential (∃).

Universal Quantification (∀x)

The assertion that a property holds for all elements in a certain domain.

Existential Quantification (∃x)

The assertion that there exists at least one element in a certain domain for which a property holds.

Soundness

The property of a logical system that ensures if a statement can be proved, it is true.

Completeness

The property of a logical system that ensures if a statement is true, it can be proved.

Semantic Equivalence (≡)

A relationship between two statements indicating they have the same meaning in every possible interpretation.

Proof by Contradiction

A method of proof where one assumes the negation of what is to be proven and shows that this assumption leads to a contradiction.

Resolution Calculus

A rule of inference used for propositional logic and predicate logic that allows for deriving conclusions from premises.