DISCRETE STRUCTURES NOTES

Propositional Logic

Statements that contain no variables and are either always true or false.

George Boole

Mathematician who used symbols like p, q, r, and s to represent simple statements.

Proposition

A statement that is either true or false, such as "Today is Friday."

Non-proposition

A statement that contains variables or commands, such as "2 plus y equals 10."

Logical Operators

Symbols (¬, ∧, ⊕, ∨, →, ↔) used to form compound propositions.

Truth Value

The truth value of a statement is either true (T or 1) or false (F or 0).

Truth Table

A table that shows the truth value of a compound statement for all possible truth values of its simple statements.

Logical Equivalence

Two statements are equivalent if they have the same truth value for all possible truth values of their simple statements.

Tautology

A compound proposition that is always true, regardless of the truth values of its components.

Contradiction

A compound proposition that is always false.

Contingency

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

Argument

A set of statements consisting of premises and a conclusion.

Valid Argument

An argument where the conclusion is true whenever all premises are true.

Invalid Argument

An argument where the conclusion is false in any case where all premises are true.

Predicate

A statement that contains a variable, such as P(x).

Universe of Discourse

The specific set of values for a variable in predicate logic.

Quantifiers

Symbols (∀ for "for all" and ∃ for "there exists") used to express propositions about predicates.

Universal Quantifier (∀)

Indicates that a predicate is true for all elements in a set.

Existential Quantifier (∃)

Indicates that a predicate is true for at least one element in a set.