Lecture 1 - Propositions and Propositional Logic

Proposition

A declarative statement that is either true or false, but not a question, command, or exclamation.

Logical Connectives

Symbols that connect propositions to form more complex statements.

Conjunction

Logical connective represented by 'And' (p ∧ q); true only if both propositions are true.

Disjunction

Logical connective represented by 'Or' (p ∨ q); true if at least one of the propositions is true.

Exclusive OR (XOR)

Logical connective represented by 'XOR' (p ⊕ q); true if both of the propositions are true, or both of them are false (cannot be one or the other).

Negation

Logical operation represented by 'Not' (¬p); reverses the truth value of the proposition.

Conditional

Logical implication represented by 'If-Then' (p → q); false only when p is true and q is false.

Biconditional

Logical connective represented by 'If and Only if' (p ↔ q); true when both propositions have the same truth values.

Truth Table

A tabular representation of the truth values of propositions under various conditions.

Rows for a truth table (how to find)

Expressed by 2ⁿ number of variables

Columns for a truth table (how to find)

Expressed by n + m, where n is the number of variables and m is the number of operations (+,¬ →, etc.)

Filling out a truth table (process)

Start with the variable columns

Fill the rightmost column (single variable) with one alternating T/F value

Fill the column directly to the left with two alternating T/F values (TT/FF)

Continue alternating with double the number of T/F values until there are no more columns to the left

Fill out all the remaining truth table values by applying the defined operations

Operator Precedence

The order in which logical operations are evaluated, from highest to lowest.

Equivalence

Two logical statements that have the same truth values in all scenarios.

Non-proposition

Statements that cannot be classified as true or false, such as questions or commands.

Truth condition

The specific conditions under which a logical connective produces a true or false outcome.

Converse of a Conditional

The reverse of a conditional statement, represented as q → p; not necessarily true.

Translation of propositions

The process of converting English statements into logical expressions.