Chapter 1: Formal Logic
Section 1.1 Statements, Symbolic Representation and Tautologies
Formal Symbols of Propositional Logic
Logic is a fundamental concept in computing, serving as the essential framework that governs how computers process and manipulate data, make informed decisions, and execute a wide range of instructions. By utilizing logical principles and operations, computers are able to perform everything from simple arithmetic calculations to complex problem-solving tasks. The underlying binary logic, which is based on true and false values (represented as 1s and 0s), enables computers to process vast amounts of information accurately and efficiently. This logical foundation allows computers to determine the appropriate actions to take, control the flow of programs, and carry out sequences of operations that drive the functionality of both hardware and software.Formal Logic History
Logic has been studied since the classical Greek period ( 600-300BC). The Greeks, most notably Thales was the first to formally analyze the reasoning process.Aristotle (384-322BC), the "father of logic", and many other Greeks searched for universal truths that were irrefutable. Aristotle developed the first system of formal logic, known as syllogistic logic, which focuses on the logical relationships between statements, or propositions. A syllogism is a form of reasoning where a conclusion is drawn from two given or assumed propositions (premises). This form of logic is foundational and was the dominant system of logic until the development of modern symbolic logic in the 19th century.
A second great period for logic came with the use of symbols to simplify complicated logical arguments. Gottfried Leibniz (1646-1716) began this work at age 14, but failed to provide a workable foundation for symbolic logic.
George Boole (1815-1864) is considered the "father of symbolic logic" due to his groundbreaking work in the development of a system of logic that uses symbols and algebraic methods to represent and analyze logical statements. Boole's work laid the foundation for modern mathematical logic and had a profound impact on the fields of mathematics, computer science, and philosophy. He developed logic as an abstract mathematical system consisting of defined terms (propositions), operations (conjunction, disjunction, and negation), and rules for using the operations. It is this system that we will study in the first section.
Logic provides a powerful tool for reasoning correctly about mathematics, algorithms and computers. It is used extensively throughout computer science, and you need to understand its basic concepts in order to study many of the more advanced subjects in computing.
Propositional Logic, also known as sentential logic or statement logic, is a branch of logic that deals with propositions (statements) that can be either true or false, but not both. It focuses on the logical relationships and operations between propositions using logical connectives.
Proposition
Formal logic can represent the statements we use in English to communicate facts or information. A statement (or proposition) is a sentence that is either true or false.A proposition is a statement that is, either true or false -- not both.
Some Sample Propositions
• MTSU is in Murfreesboro. ✓• The Earth orbits the Sun. ✓
• 4 > 9 ✓
• Is this CSCI 3080? No (Question)
• Close the door. No (Command)
• Oatmeal is slimy No (Opinion)
• x > y No (depends on x and y; sometime are true, sometimes are wrong)
Things that aren't propositions
• Commands cannot be true or false.• Questions cannot be true or false.
• Jibberish cannot be true or false.
• Suggestions or Recommendations cannot be true or false.
Propositional Logic
Propositional logic is a mathematical system for reasoning about propositions and how they relate to one another.⭐ Propositional logic is a formal mathematical system whose syntax is rigidly specified.
⭐ Every statement in propositional logic consists of propositional variables combined via logical connectives .
Propositional logic is a branch of logic that deals with propositions, which are statements that can be either true or false. It is the foundation of formal logic and is often used in mathematical reasoning, computer science, and philosophy. Propositional logic focuses on the relationships between propositions and how they can be combined and manipulated using logical connectives to form more complex statements.
Propositional Variables
❊ Each proposition will be represented by a propositional variable❊ Propositional variables are usually represented as capital-case letters, such as \(A\), \(B\), \(C\), \(D\), etc. If we need more, we can use subscripts: \(A_1\), \(A_2\), etc.
❊ Each variable can take one one of two values: true or false.
Logical Connectives
❊ Logical NOT: ¬A- • Read "not A"
- • ¬A is true if and only if A is false
- • Also called logical negation
| \(A\) | \(¬A\) |
|---|---|
| F | T |
| T | F |
❊ Logical AND: A ∧ B
- • Read "A and B"
- • A ∧ B is true if both A and B are true
- • Also called logical conjunction
| \(A\) | \(B\) | \(A ∧ B\) |
|---|---|---|
| F | F | F |
| F | T | F |
| T | F | F |
| T | T | T |
❊ Logical OR: A ∨ B
- • Read "A or B"
- • A ∨ B is true if at least one of A or B are true (inclusive OR)
- • Also called logical disjunction
| \(A\) | \(B\) | \(A ∨ B\) |
|---|---|---|
| F | F | F |
| F | T | T |
| T | F | T |
| T | T | T |
❊ Logical XOR: A ⊕ B
- • Read "A Exclusive OR B"
- • A ⊕ B is true if one, but not both, of the conditions are true. (exclusive OR)
- • Also called Exclusive Disjunction
| \(A\) | \(B\) | \(A ⊕ B\) |
|---|---|---|
| F | F | F |
| F | T | T |
| T | F | T |
| T | T | F |
❊ Implication: A → B
- • Read "A implies B"
- • A → B means "if A is true, then B is true as well."
- • It conveys the meaning that the truth of A implies or leads to the truth of B.
- • A stands for the antecedent statement and B stands for the consequent statement.
- • A → B says nothing about what happens if A is false.
- • A → B says nothing about causality; it just says that if A is true, B will be true as well.
| \(A\) | \(B\) | \(A → B\) |
|---|---|---|
| F | F | T |
| F | T | T |
| T | F | F |
| T | T | T |
The truth table for implication is less obvious than that for conjunction or disjunction. To understand its definition, let's suppose your friend remarks, "if I pass my economics test, then I'll go to the movie Friday." If your friend passes the test and goes to the movie, the remark was true. If your friend passes the test but doesn't go to the movie, the remark was false. If your friend doesn't pass the test, then-whether he or she goes to the movie or not-- you could not claim that the remark was false. By convention, \(A → B\) is considered true if A is false, regardless of the truth value of B.
❊ Equivalence (Biconditional): A ↔ B
- • A ↔ B means "A if and only if B"
- • The expression A ↔ B stands for (A → B) ∧ (B → A).
- • Intuitively, either both \(A\) and \(B\) are true, or neither of them are.
| \(A\) | \(B\) | \(A ↔ B\) |
|---|---|---|
| F | F | T |
| F | T | F |
| T | F | F |
| T | T | T |
Unlike conjunction, disjunction, and implication, the equivalence connective is not really a fundamental connective but a convenient shortcut. The expression \(A ↔ B\) stands for \((A → B) ∧ (B → A)\). We can write the truth table for equivalence by constructing, one piece at a time, a truth table for \( (A → B) ∧ (B → A) \). From the following truth table, \(A ↔ B\) is true exactly when A and B have the same truth value.
| \(A\) | \(B\) | \(A → B\) | \(B → A\) | \((A → B) ∧ (B → A) \) |
|---|---|---|---|---|
| F | F | T | T | T |
| F | T | T | F | F |
| T | F | F | T | F |
| T | T | T | T | T |
How many rows for truth table?
| Number of variables | Number of rows |
|---|---|
| 1 | 2 |
| 2 | 4 |
| 3 | 8 |
| 4 | 16 |
| ... | ... |
| \(n\) | \(2^n\) |
| Truth Table Pattern for Three Variables | ||
|---|---|---|
| A | B | C |
| T | T | T |
| T | T | F |
| T | F | T |
| T | F | F |
| F | T | T |
| F | T | F |
| F | F | T |
| F | F | F |
Why this matters for Computer Science
- Computers work with binary states (0/1, T/F), which are discrete.
- Boolean algebra and propositional logic form the foundation of:
- Digital circuits
- Programming conditions
- Database queries
- Formal verification
Reference
Mathematical LogicLogic