Chapter 1-3

Proposition

A declarative sentence that is either true or false.

Propositional Variable

A symbol such as p, q, r, used to represent a proposition.

T

The proposition that is always true.

F

The proposition that is always false.

Compound Proposition

A statement constructed from logical connectives and other propositions.

Negation Symbol

¬ denotes the operation that reverses the truth value of a proposition.

Negation

The operation that takes a proposition p and forms ¬p, which is true when p is false and false when p is true.

Conjunction Symbol

∧ denotes the logical 'and' operation.

Conjunction

The operation that forms p ∧ q, which is true when both p and q are true, and false otherwise.

Disjunction Symbol

∨ denotes the logical 'or' operation.

Disjunction

The operation that forms p ∨ q, which is true if at least one of p or q is true, and false only if both are false.

Inclusive Or

A disjunction that is true if either or both propositions are true.

Exclusive Or Symbol

⊕ denotes the 'xor' operation.

Exclusive Or

An operation where p ⊕ q is true when exactly one of p or q is true, and false when both are true or both are false.

Implication Symbol

→ denotes the conditional 'if…then…' operation.

Implication

The conditional statement p → q is false only when p is true and q is false; true otherwise.

Hypothesis (Implication)

The antecedent or premise of a conditional statement p → q.

Conclusion (Implication)

The consequent or result in a conditional statement p → q.

Converse

The proposition q → p formed from p → q by interchanging antecedent and consequent.

Contrapositive

The proposition ¬q → ¬p formed from p → q by negating and swapping antecedent and consequent.

Inverse

The proposition ¬p → ¬q formed from p → q by negating both antecedent and consequent.

Biconditional Symbol

↔ denotes the 'if and only if' operation.

Biconditional

The statement p ↔ q is true when p and q share the same truth value, true or false.

Truth Table

A tabular method of representing truth values of propositions for all possible combinations of truth values of atomic propositions.

Logically Equivalent

Two compound propositions are logically equivalent if they always have the same truth value.

Equivalence Symbol

⇔ or ≡ expresses that two propositions are logically equivalent.

Precedence of Logical Operators

Ordering of logical operations: 1) ¬, 2) ∧, 3) ∨, 4) →, 5) ↔.

System Specification

A list of propositions describing system requirements using logic.

Consistent Specifications

A set of propositions is consistent if truth values can be assigned to make all true.

Knight (Logic Puzzle)

An inhabitant who always tells the truth.

Knave (Logic Puzzle)

An inhabitant who always lies.

Logic Circuit

An electronic circuit where signals correspond to truth values; 0 stands for false and 1 stands for true.

Inverter (NOT Gate)

A gate that outputs the negation of its input bit.

OR Gate

A gate that outputs true if at least one input bit is true.

AND Gate

A gate that outputs true only if both input bits are true.

Tautology

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

Contradiction

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

Contingency

A proposition that is sometimes true and sometimes false, depending on the truth values of its components.

De Morgan's Laws

Rules relating conjunctions and disjunctions through negation: ¬(p ∨ q) ≡ (¬p ∧ ¬q), ¬(p ∧ q) ≡ (¬p ∨ ¬q).

Identity Laws

Logical laws stating p ∧ T ≡ p and p ∨ F ≡ p.

Domination Laws

Logical laws stating p ∨ T ≡ T and p ∧ F ≡ F.

Idempotent Laws

Logical laws stating p ∨ p ≡ p and p ∧ p ≡ p.

Double Negation Law

Logical law stating ¬(¬p) ≡ p.

Negation Laws

Logical laws such as p ∨ ¬p ≡ T and p ∧ ¬p ≡ F.

Commutative Laws

Logical laws such as p ∨ q ≡ q ∨ p and p ∧ q ≡ q ∧ p.

Associative Laws

Logical laws such as (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) and (p ∧ q) ∧ r ≡ p ∧ (q ∧ r).

Distributive Laws

Logical laws such as p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r).

Absorption Laws

Logical laws expressing relationships like p ∨ (p ∧ q) ≡ p and p ∧ (p ∨ q) ≡ p.

Propositional Logic

A system of logic that uses propositions, which are statements that are either true or false, but cannot express relationships or properties of objects.

Predicate Logic

A system of logic extending propositional logic using variables, predicates, and quantifiers to express properties and relationships involving objects; statements have truth values when variables are specified or bound.

Variable

A symbol such as x, y, or z that represents an element from a domain in predicate logic; does not have a definite truth value until specified or quantified.

Predicate

A function or property like Px (read as "P of x") that assigns a truth value to each element in its domain based on some property.

Propositional Function

An expression containing variables and a predicate, e.g., Px; it becomes a proposition (true or false) when all variables are assigned values or bound by quantifiers.

Domain

The set of all possible values that variables may represent in predicate logic, often denoted by U.

Truth Value

The property of a logical expression that it is either true or false; truth values are determined once variables are specified or bound.

Universal Quantifier

The logical symbol ∀ ("for all") expressing that a property holds for every element in the domain; a statement with ∀ is true if it holds for all cases, false if there exists at least one counterexample.

Existential Quantifier

The logical symbol ∃ ("there exists") expressing that a property holds for at least one element in the domain; a statement with ∃ is true if there is at least one instance, false if none exist.

Bound Variable

A variable in a predicate logic expression that is associated with a quantifier; its value is determined within the scope of that quantifier.

Compound Expression

A logical expression combining predicates or propositional functions using logical connectives such as ∧ (and), ∨ (or), ¬ (not); may or may not have truth values depending on variable assignment.

Logical Connective

A symbol such as ∧ (and), ∨ (or), ¬ (not), → (implies), or ↔ (if and only if) used to construct compound logical expressions.

Unique Quantifier

The symbol !x or "there is a unique x such that" Px, meaning Px is true for exactly one x in the domain; true if one unique value satisfies, false otherwise.

Propositional Equality

The assertion that two logical statements S and T are logically equivalent, denoted S ≡ T; means they have the same truth value for all domains and predicates.

Precedence of Quantifiers

Rule stating that quantifiers ∀ and ∃ take higher priority than logical connectives in compound statements.

Nested Quantifier

A logical statement where quantifiers appear within the scope of other quantifiers (e.g., ∀x ∃y Px, y); the truth value may depend on order and nesting.

Negation of Quantifiers

Rules for negating quantified statements: ¬∀x Px is equivalent to ∃x ¬Px (not all is some not) and ¬∃x Px is equivalent to ∀x ¬Px (not exists is all not).

Conjunction as Quantification

In finite domains, the statement ∀x Px is equivalent to the conjunction Px₁ ∧ Px₂ ∧…; true if all are true, false if any is false.

Disjunction as Quantification

In finite domains, the statement ∃x Px is equivalent to the disjunction Px₁ ∨ Px₂ ∨…; true if any is true, false if all are false.

Translation to Predicate Logic

The process of expressing statements from English into predicate logic using variables, predicates, and quantifiers to capture meaning and truth.

Order of Quantifiers

The concept that the sequence in which quantifiers appear (such as ∀x∃y Px, y versus ∃y∀x Px, y) affects the statement’s meaning and truth value.

System Specification

Application of predicate logic for expressing system requirements, such as "every mail message larger than one megabyte will be compressed," translated using predicates and quantifiers.

De Morgan's Laws for Quantifiers

Rules for distributing negation over quantifiers: ¬∀x Px ≡ ∃x ¬Px and ¬∃x Px ≡ ∀x ¬Px, switching quantifier type and applying negation to the inner statement.

Propositional Logic

A branch of logic dealing with propositions, which can be either true or false, and logical connectives.

Premises

All propositions in an argument except the final one; used to draw a conclusion that can be true or false.

Conclusion

The last statement in an argument, whose truth or falsehood is inferred from the premises.

Argument Form

An argument that remains valid regardless of the specific true or false propositions substituted.

Tautology

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

Inference Rules

Simple valid argument forms used to construct more complex arguments; determine truth or falsehood.

Modus Ponens

(p ∧ (p →q)) → q; if p is true and p implies q, then q is true.

Modus Tollens

(¬q∧(p →q))→¬p; if p implies q and q is false, then p is false.

Hypothetical Syllogism

((p →q) ∧(q→r))→(p→ r); if p implies q and q implies r, then p implies r is true.

Disjunctive Syllogism

(¬p∧(p ∨q))→q; if either p or q is true and p is false, then q must be true.

Addition

p →(p ∨q); if p is true, then either p or q is true.

Simplification

(p∧q) →p; if p and q are both true, then p is true.

Conjunction

((p) ∧ (q)) →(p ∧ q); if p is true and q is true, then p and q together are true.

Resolution

((¬p ∨ r ) ∧ (p ∨ q)) →(q ∨ r); combines premises to conclude a new disjunction that is true.

Valid Argument

A sequence of statements, each a premise or derived from previous statements, ending in a true or false conclusion.

Quantified Statements

Statements containing variables and quantifiers that can be true or false for elements in a domain.

Universal Instantiation (UI)

A rule allowing the inference that a property true for all elements applies to a particular instance.

Universal Generalization (UG)

A rule inferring that if a property is true for an arbitrary element, it is true for all elements; true for all.

Existential Instantiation (EI)

Allows inference from a statement of existence to a particular instance for which the statement is true.

Existential Generalization (EG)

A rule inferring from a particular case the existence of an element with a specified property; at least one is true.

Universal Modus Ponens

Combines universal instantiation and modus ponens; if a universal statement and an instance are true, conclusion is true.

Proof

A valid argument establishing the truth of a statement, showing it must be true.

Theorem

A statement proved to be true using definitions, axioms, other theorems, or inference rules.

Lemma

A helping theorem or intermediate result needed to prove another theorem; its truth is established.

Corollary

A result that follows directly from a theorem; its truth is derived from a previously proven statement.

Proposition

A less important theorem whose truth or falsity can be proved.

Conjecture

A statement proposed to be true; once a proof is found, it becomes a theorem or else may be false.

Even Integer

An integer n is even if there exists an integer k such that n = 2k; n is true for some k.

Odd Integer

An integer n is odd if there exists an integer k such that n = 2k + 1; n is true for some k.