Propositional Logic Study Notes

Foundations of Logic and Proofs

• The rules of logic define the precise meaning of mathematical statements and are used to distinguish between valid and invalid mathematical arguments.

• Logic serves as the fundamental basis for all mathematical reasoning and automated reasoning.

• Mathematical arguments used to prove a statement is true are called proofs. Once a statement is proven, it is referred to as a theorem.

• Applications of logic in computer science include:

  • The design of computing machines and computer circuits.

  • The specification of systems.

  • Artificial intelligence.

  • Computer programming and development of programming languages.

  • Establishing the security of a system.

  • Verifying that algorithms and computer programs produce correct results for all possible inputs.

• Automated reasoning systems allow computers to construct their own proofs.

• A conjecture is a statement proposed to be true but not yet proven. Studying conjectures is a primary method for developing mathematical knowledge.

Propositional Logic and Propositions

• Propositional logic (or propositional calculus) is the branch of logic that deals with propositions. It was first developed systematically by the Greek philosopher Aristotle more than 2300 years ago.

• Definition: A proposition is a declarative sentence (a sentence declaring a fact) that is either true or false, but not both.

• The truth value of a proposition is denoted as T (true) or F (false).

• Examples of propositions:

  • "Washington, D.C., is the capital of the United States of America." (Truth value: T)

  • "Toronto is the capital of Canada." (Truth value: F)

  • "$1 + 1 = 2$" (Truth value: T)

  • "$2 + 2 = 3$" (Truth value: F)

• Sentences that are not propositions:

  • Questions: "What time is it?"

  • Commands: "Read this carefully."

  • Sentences with variables: "$x + 1 = 2$" and "$x + y = z$" are not propositions because they are neither true nor false until values are assigned to the variables.

• Propositional variables (or statement variables) are letters used to represent propositions, such as $p$, $q$, $r$, and $s$.

Biography: Aristotle (384 B.C.E.–322 B.C.E.)

• Born in Stagirus (Stagira) in northern Greece; his father was the personal physician to the King of Macedonia.

• At age 17, he was sent to Athens and joined Plato’s Academy, where he remained for 20 years.

• He tutored Alexander (later Alexander the Great), the son of King Philip of Macedonia, for five years.

• He founded his own school, the Lyceum, in Athens. His followers were called "peripatetics" ("to walk about") because Aristotle walked while discussing philosophy.

• Following the death of Alexander the Great in 323 B.C.E., he fled to Chalcis to avoid charges of impiety, where he died a year later of a stomach ailment.

• His works spanned logic, philosophy, psychology, physics, and natural history. His writings were preserved in a vault and rediscovered roughly 200 years later by a book collector, eventually being issued in new editions in Rome.

Compound Propositions and Logical Operators

• New propositions, called compound propositions, are formed from existing propositions using logical operators (also called connectives).

• The methods for producing compound propositions were discussed by George Boole in 1854 in his book The Laws of Thought.

Negation

• Definition: Let $p$ be a proposition. The negation of $p$, denoted by $p$ (or ${p}$), is the statement "It is not the case that $p$."

• The truth value of $p$ is the opposite of the truth value of $p$.

• Example: The negation of "Michael’s PC runs Linux" is "Michael’s PC does not run Linux."

• Example: The negation of "Vandana’s smartphone has at least 32GB of memory" is "Vandana’s smartphone has less than 32GB of memory."

Conjunction

• Definition: The conjunction of $p$ and $q$, denoted by $p \wedge q$, is the proposition "$p$ and $q$."

• The conjunction $p \wedge q$ is true when both $p$ and $q$ are true and is false otherwise.

• In natural language, the word "but" is often used similarly to "and" in a conjunction (e.g., "The sun is shining, but it is raining").

Disjunction

• Definition: The disjunction of $p$ and $q$, denoted by $p \vee q$, is the proposition "$p$ or $q$."

• The disjunction $p \vee q$ is false when both $p$ and $q$ are false and is true otherwise (at least one is true).

• Inclusive vs. Exclusive Or:

  • Inclusive Or (disjunction): True if either or both propositions are true. Example: "Students who have taken calculus or computer science can take this class."

  • Exclusive Or: True if exactly one of the propositions is true. Example: "Soup or salad comes with an entre." (meaning you cannot have both).

Exclusive Or (XOR)

• Definition: The exclusive or of $p$ and $q$, denoted by $p \oplus q$, is the proposition that is true when exactly one of $p$ and $q$ is true and is false otherwise.

Biography: George Boole (1815–1864)

• A self-taught mathematician born in Lincoln, England, and the son of a cobbler.

• Published The Mathematical Analysis of Logic in 1848.

• Appointed professor of mathematics at Queen’s College in Cork, Ireland, in 1849.

• Best known for his 1854 work, The Laws of Thought, which introduced Boolean algebra.

• He died of pneumonia in 1864 after walking to a lecture in a rainstorm and becoming soaking wet.

Conditional Statements

• Definition: The conditional statement $p \rightarrow q$ is the proposition "if $p$, then q$."\n* The conditional statement is false only when p$is true and$q is false; it is true otherwise.\n* p is called the hypothesis (or antecedent or premise).\n* q is called the conclusion (or consequence).\n\n## Terminology for p \rightarrow q\n* "if p$, then$q"\n* "p$implies$q"\n* "p$only if$q"\n* "p$is sufficient for$q"\n* "q$when$p"\n* "q$is necessary for$p"\n* "q$unless$p"\n* Understanding "p$only if$q$": This means$p$cannot be true when$q$is false. If$p$is false, the statement says nothing about$q.\n* Understanding "q$unless$p$": This means if$p$is false (meaning$p$is true), then$q must be true.\n\n## Conditional Statements in Logic vs. English\n* In natural language, conditional statements usually imply a cause-and-effect relationship.\n* In mathematical reasoning, p \rightarrow q$is defined solely by truth values. For example, "If Juan has a smartphone, then$2 + 3 = 5" is considered a true conditional statement simply because the conclusion is true.\n\n## Programming Language "If-Then"\n* The `if p then S` construction in programming is an instruction, not a proposition. \n* Segment S$is executed if$p$is true, but not if$p is false.\n\n# Derived Conditional Statements\n\n* Converse: The converse of p \rightarrow q$is the proposition$q \rightarrow p.\n* Contrapositive: The contrapositive of p \rightarrow q$is the proposition$q \rightarrow p.\n* Inverse: The inverse of p \rightarrow q$is the proposition$p \rightarrow q.\n* Equivalence:\n * The contrapositive always has the same truth value as the original conditional statement (p \rightarrow q).\n * The converse and the inverse are equivalent to each other, but they are NOT equivalent to the original statement p \rightarrow q.\n\n# Biconditional Statements\n\n* Definition: The biconditional statement p \leftrightarrow q$is the proposition "$p$if and only if$q$."

• The biconditional is true when $p$ and $q$ have the same truth values (both T or both F) and is false otherwise.

• Also known as bi-implications.

• Abbreviation: "iff" stands for "if and only if."

• $p \leftrightarrow q$ has the same truth value as $(p \rightarrow q) \wedge (q \rightarrow p)$.

• Common terminology:

  • "$p$ is necessary and sufficient for $q$"

  • "if $p$ then $q$, and conversely"

Truth Tables and Operator Precedence

• Truth tables determine the truth values of compound propositions by evaluating sub-expressions for all combinations of variable truth values.

• Precedence rules reduce the number of parentheses needed:

  1. Negation: $$

  2. Conjunction: $\wedge$

  3. Disjunction: $\vee$

  4. Conditional: $\rightarrow$

  5. Biconditional: $\leftrightarrow$

• Example: $p \wedge q$ means $(p) \wedge q$, not $(p \wedge q)$.

• Example: $p \wedge q \vee r$ is evaluated as $(p \wedge q) \vee r$.

Logic and Bit Operations

• A bit is a binary digit: 0 (zero) or 1 (one). The term was introduced by John Tukey in 1946.

• Truth values are represented by bits: 1 for T (True) and 0 for F (False).

• A Boolean variable is a variable with a value of either true or false.

• Bit Operators:

  • OR corresponds to $\vee$

  • AND corresponds to $\wedge$

  • XOR corresponds to $\oplus$

• Bit Strings:

  • Definition: A sequence of zero or more bits.

  • Length: The number of bits in the string.

  • Bitwise operations (OR, AND, XOR) are performed on strings of the same length by operating on each pair of bits in corresponding positions.

Biography: John Wilder Tukey (1915–2000)

• American statistician who coined the terms "bit" and "software."

• Studied chemistry and mathematics at Brown University and received a Ph.D. from Princeton in 1939.

• Founded the Statistics Department at Princeton in 1966.

• Known for developing the fast Fourier transform with J. W. Cooley.

• Received the National Medal of Science and served on the President’s Science Advisory Committee.

Summary of Truth Tables

Logical Connectives Truth Values

Bitwise Operator Truth Values