Basic Truth tables and propositional functions

# Basic Truth tables and propositional functions ## The Truth-Table ### Introduction Welcome to the exciting world of logic! In this lesson, we will explore truth tables, a fundamental tool in propositional logic. Truth tables allow us to systematically determine the truth value of complex statements, called compound propositions, based on the truth values of their simpler components. Understanding truth tables is crucial for evaluating arguments, designing circuits, and thinking clearly. ### Key Concepts #### What is a Truth Table? A truth table is a mathematical table used in logic, specifically in connection with Boolean algebra and Boolean functions, to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of truth values taken by their propositional variables. * **Proposition:** A statement that is either true or false, but not both. For example, "The sky is blue" is a proposition. "What time is it?" is not. * **Truth Value:** The state of a proposition being either **True (T)** or **False (F)**. * **Compound Proposition:** A proposition formed by combining two or more simple propositions using logical connectives. #### Basic Logical Connectives Logical connectives are symbols or words used to connect two or more sentences (or propositions) in a grammatically valid way, such that the truth value of the resulting compound proposition is determined by the truth values of the original propositions and the meaning of the connective. ##### 1. Conjunction (AND) * **Symbol:** \( \land \) (read as "and") * **Meaning:** The compound proposition \( P \land Q \) is true if and only if both \( P \) and \( Q \) are true. * **Example:** "It is raining AND the sun is shining." * **Truth Table for \( P \land Q \)** | P | Q | \( P \land Q \) | | :---- | :---- | :---------- | | T | T | T | | T | F | F | | F | T | F | | F | F | F | ##### 2. Disjunction (OR) * **Symbol:** \( \lor \) (read as "or") * **Meaning:** The compound proposition \( P \lor Q \) is true if at least one of \( P \) or \( Q \) is true (or both are true). This is an inclusive OR. * **Example:** "I will eat pizza OR I will eat pasta." * **Truth Table for \( P \lor Q \)** | P | Q | \( P \lor Q \) | | :---- | :---- | :---------- | | T | T | T | | T | F | T | | F | T | T | | F | F | F | ##### 3. Negation (NOT) * **Symbol:** \( \neg \) (read as "not") * **Meaning:** The negation of a proposition \( P \), denoted \( \neg P \), is true if \( P \) is false, and false if \( P \) is true. It reverses the truth value. * **Example:** If \( P \) is "The cat is black", then \( \neg P \) is "The cat is NOT black." * **Truth Table for \( \neg P \)** | P | \( \neg P \) | | :---- | :----- | | T | F | | F | T | ##### 4. Implication (Conditional IF...THEN) * **Symbol:** \( \to \) (read as "if...then...") * **Meaning:** The compound proposition \( P \to Q \) (read "If P, then Q") is false if and only if \( P \) is true and \( Q \) is false. In all other cases, it is true. * \( P \) is called the **antecedent** (or hypothesis). * \( Q \) is called the **consequent** (or conclusion). * **Example:** "IF it rains, THEN the ground gets wet." * **Truth Table for \( P \to Q \)** | P | Q | \( P \to Q \) | | :---- | :---- | :---------- | | T | T | T | | T | F | F | | F | T | T | | F | F | T | ##### 5. Biconditional (IF AND ONLY IF) * **Symbol:** \( \leftrightarrow \) (read as "if and only if" or "iff") * **Meaning:** The compound proposition \( P \leftrightarrow Q \) is true if and only if \( P \) and \( Q \) have the same truth value (both true or both false). * **Example:** "I will pass the exam IF AND ONLY IF I study hard." * **Truth Table for \( P \leftrightarrow Q \)** | P | Q | \( P \leftrightarrow Q \) | | :---- | :---- | :--------------- | | T | T | T | | T | F | F | | F | T | F | | F | F | T | #### How to Construct a Truth Table Follow these steps to build a truth table for any compound proposition: 1. **Identify Simple Propositions:** Determine all the individual propositions (e.g., P, Q, R) in the compound statement. 2. **Determine Number of Rows:** The number of rows in your truth table will be \( 2^n \), where \( n \) is the number of simple propositions. For example, if you have 2 propositions (P, Q), you will have \( 2^2 = 4 \) rows. If you have 3 (P, Q, R), you will have \( 2^3 = 8 \) rows. 3. **Create Columns for Simple Propositions:** List each simple proposition in its own column. Fill the truth values systematically to cover all possible combinations. A common method is to alternate T/F for the last proposition, TT/FF for the second to last, TTTT/FFFF for the third to last, and so on. 4. **Create Columns for Sub-expressions:** Break down the compound proposition into its smaller logical components. Create a column for each sub-expression and evaluate its truth value based on the truth values of the propositions it contains and the rules of the logical connective. 5. **Create Column for the Final Compound Proposition:** Finally, create a column for the entire compound proposition and evaluate its truth value based on the results of the sub-expressions. #### Propositional Functions A propositional function is a statement containing one or more variables, such that when specific values are substituted for the variables, it becomes a proposition (i.e., a statement that is either true or false). * **Example:** Let \( P(x) \) be the statement "x is an even number." * If \( x = 4 \), then \( P(4) \) is "4 is an even number," which is **True**. * If \( x = 3 \), then \( P(3) \) is "3 is an even number," which is **False**. ### Vocabulary * **Proposition:** A declarative sentence that is either true or false, but not both. * **Truth Value:** The status of a proposition as being true or false. * **Compound Proposition:** A proposition formed by combining two or more simple propositions. * **Logical Connective:** A symbol or word (like AND, OR, NOT, IF...THEN, IF AND ONLY IF) used to join simple propositions. * **Conjunction:** The logical connective "AND" (\( \land \)). * **Disjunction:** The logical connective "OR" (\( \lor \)). * **Negation:** The logical connective "NOT" (\( \neg \)). * **Implication (Conditional):** The logical connective "IF...THEN" (\( \to \)). * **Biconditional:** The logical connective "IF AND ONLY IF" (\( \leftrightarrow \)). * **Antecedent:** The 'P' part of an implication (the 'if' clause). * **Consequent:** The 'Q' part of an implication (the 'then' clause). * **Tautology:** A compound proposition that is always true, regardless of the truth values of its component propositions. * **Contradiction:** A compound proposition that is always false, regardless of the truth values of its component propositions. * **Contingency:** A compound proposition that is neither a tautology nor a contradiction (it can be true or false depending on the truth values of its components). * **Propositional Function:** A statement containing one or more variables that becomes a proposition when variables are replaced by specific values. ### Examples #### Example 1: Constructing a Truth Table for \( P \land (\neg Q) \) 1. **Simple Propositions:** P, Q (n=2, so \( 2^2 = 4 \) rows). 2. **Steps:** * Column for P * Column for Q * Column for \( \neg Q \) * Column for \( P \land (\neg Q) \) | P | Q | \( \neg Q \) | \( P \land (\neg Q) \) | | :---- | :---- | :------- | :--------------- | | T | T | F | F | | T | F | T | T | | F | T | F | F | | F | F | T | F | #### Example 2: Constructing a Truth Table for \( (P \lor Q) \to \neg R \) 1. **Simple Propositions:** P, Q, R (n=3, so \( 2^3 = 8 \) rows). 2. **Steps:** * Columns for P, Q, R * Column for \( P \lor Q \) * Column for \( \neg R \) * Column for \( (P \lor Q) \to \neg R \) | P | Q | R | \( P \lor Q \) | \( \neg R \) | \( (P \lor Q) \to \neg R \) | | :---- | :---- | :---- | :--------- | :------- | :--------------------- | | T | T | T | T | F | F | | T | T | F | T | T | T | | T | F | T | T | F | F | | T | F | F | T | T | T | | F | T | T | T | F | F | | F | T | F | T | T | T | | F | F | T | F | F | T | | F | F | F | F | T | T | #### Example 3: Propositional Function Evaluation Let \( Q(y) \) be the statement "y is a capital city." * Evaluate \( Q(\text{Paris}) \): * "Paris is a capital city." (**True**) * Evaluate \( Q(\text{Nairobi}) \): * "Nairobi is a capital city." (**True**) * Evaluate \( Q(\text{Mombasa}) \): * "Mombasa is a capital city." (**False**) ### Exercises 1. Construct a truth table for the following compound proposition: \( \neg P \lor Q \) 2. Construct a truth table for the following compound proposition: \( (P \land Q) \leftrightarrow (P \lor \neg Q) \) 3. Determine if the following statement is a tautology, contradiction, or contingency using a truth table: \( (P \land \neg P) \) 4. Let \( R(z) \) be the propositional function "z > 10". * Is \( R(12) \) true or false? * Is \( R(5) \) true or false? ### Assignment 1. Construct a full truth table for the expression: \( (P \to Q) \lor (Q \land R) \) 2. Prove, using a truth table, that \( \neg (P \land Q) \) is logically equivalent to \( \neg P \lor \neg Q \) (De Morgan's Law). 3. Translate the following English statement into a logical expression using propositions and connectives: "If the alarm rings AND it is morning, THEN I will wake up, OR I will go back to sleep." (Define your simple propositions first, e.g., A = "alarm rings") 4. Consider the propositional function \( S(x, y) \): "x + y = 10". * Is \( S(3, 7) \) true or false? * Is \( S(4, 5) \) true or false? ### Summary Today, we learned about the fundamental role of truth tables in propositional logic. We explored the five basic logical connectives: Conjunction (AND, \( \land \)), Disjunction (OR, \( \lor \)), Negation (NOT, \( \neg \)), Implication (IF...THEN, \( \to \)), and Biconditional (IF AND ONLY IF, \( \leftrightarrow \)). We practised constructing truth tables systematically for compound propositions and understood how propositional functions become propositions upon variable substitution. Truth tables provide a clear and organized way to analyze the truth values of complex logical statements, forming the backbone of logical reasoning. ## Logical Constants ### Introduction Welcome to our lesson on Logical Constants! In logic, just like in algebra where you use symbols for numbers and operations, we use symbols to represent specific logical relationships between statements. These special symbols are called logical constants or connectives. They are the building blocks that allow us to combine simple statements into more complex ones and analyze their truth values systematically. Understanding logical constants is fundamental to constructing and interpreting truth tables, which are powerful tools for evaluating the validity of arguments. ### Key Concepts #### What are Logical Constants? Logical constants, also known as logical connectives, are symbols used to connect or modify simple propositions (statements) to form more complex compound propositions. Unlike propositional variables (like \(P\), \(Q\), \(R\)) which stand for entire statements, logical constants represent the *relationship* or *operation* between these statements. #### The Five Basic Logical Constants (Connectives) There are five primary logical constants that form the foundation of propositional logic. Each has a specific meaning and a distinct truth table. ##### 1. Negation (NOT) * **Symbol:** \(\neg\) (read as "not") or \(\sim\) * **Meaning:** The negation of a proposition reverses its truth value. If a proposition is true, its negation is false, and vice versa. * **English Phrases:** "It is not the case that...", "not..." * **Truth Table:** | \(P\) | \(\neg P\) | | :---: | :----: | | T | F | | F | T | ##### 2. Conjunction (AND) * **Symbol:** \(\land\) (read as "and") * **Meaning:** A conjunction is true only when both propositions connected by \(\land\) are true. If even one proposition is false, the entire conjunction is false. * **English Phrases:** "and", "but", "however", "also" * **Truth Table:** | \(P\) | \(Q\) | \(P \land Q\) | | :---: | :---: | :---------: | | T | T | T | | T | F | F | | F | T | F | | F | F | F | ##### 3. Disjunction (OR) * **Symbol:** \(\lor\) (read as "or") * **Meaning:** A disjunction is true if at least one of the propositions connected by \(\lor\) is true. It is only false if *both* propositions are false. This is known as inclusive OR. * **English Phrases:** "or", "either... or..." * **Truth Table:** | \(P\) | \(Q\) | \(P \lor Q\) | | :---: | :---: | :---------: | | T | T | T | | T | F | T | | F | T | T | | F | F | F | ##### 4. Conditional (IF...THEN / Implication) * **Symbol:** \(\to\) (read as "if... then...") or \(\supset\) * **Meaning:** A conditional statement is false only when its first part (the antecedent) is true and its second part (the consequent) is false. In all other cases, it is true. * **English Phrases:** "if... then...", "...implies...", "...only if..." * **Truth Table:** | \(P\) | \(Q\) | \(P \to Q\) | | :---: | :---: | :--------: | | T | T | T | | T | F | F | | F | T | T | | F | F | T | ##### 5. Biconditional (IF AND ONLY IF / Equivalence) * **Symbol:** \(\leftrightarrow\) (read as "if and only if") or \(\equiv\) * **Meaning:** A biconditional statement is true when both propositions have the same truth value (i.e., both are true or both are false). It is false when they have different truth values. * **English Phrases:** "...if and only if...", "...is equivalent to..." * **Truth Table:** | \(P\) | \(Q\) | \(P \leftrightarrow Q\) | | :---: | :---: | :---------------: | | T | T | T | | T | F | F | | F | T | F | | F | F | T | #### Constructing Truth Tables for Compound Propositions When combining multiple logical constants, follow an order of operations similar to arithmetic: 1. **Parentheses** (innermost first) 2. **Negation** (\(\neg\)) 3. **Conjunction** (\(\land\)) and **Disjunction** (\(\lor\)) (usually left to right, or based on grouping) 4. **Conditional** (\(\to\)) 5. **Biconditional** (\(\leftrightarrow\)) ### Vocabulary * **Proposition:** A declarative sentence that is either true or false, but not both. * **Truth Value:** The state of being either true (T) or false (F). * **Logical Constant (Connective):** A symbol used to connect or modify propositions to form compound propositions. * **Negation (\(\neg\)):** The logical operation that reverses the truth value of a proposition. * **Conjunction (\(\land\)):** A compound proposition that is true only if all its component propositions are true. * **Disjunction (\(\lor\)):** A compound proposition that is true if at least one of its component propositions is true. * **Conditional (\(\to\)):** A compound proposition that is false only when its antecedent is true and its consequent is false. * **Biconditional (\(\leftrightarrow\)):** A compound proposition that is true when both component propositions have the same truth value. * **Antecedent:** The "if" part of a conditional statement (the proposition before the \(\to\)). * **Consequent:** The "then" part of a conditional statement (the proposition after the \(\to\)). ### Examples #### Example 1: Translating English to Symbolic Logic Let \(P\) = "The sun is shining." and \(Q\) = "It is hot." * "The sun is shining and it is hot." \(P \land Q\) * "It is not hot." \(\neg Q\) * "If the sun is shining, then it is hot." \(P \to Q\) * "It is hot if and only if the sun is shining." \(Q \leftrightarrow P\) * "Either the sun is not shining or it is hot." \(\neg P \lor Q\) #### Example 2: Constructing a Truth Table for a Compound Proposition Construct a truth table for \(P \land (\neg Q \to P)\). | \(P\) | \(Q\) | \(\neg Q\) | \(\neg Q \to P\) | \(P \land (\neg Q \to P)\) | | :---: | :---: | :----: | :----------: | :---------------------: | | T | T | F | T | T | | T | F | T | T | T | | F | T | F | T | F | | F | F | T | F | F | ### Exercises 1. Let \(R\) = "I study hard" and \(S\) = "I will pass the exam." Translate the following into symbolic logic: a. I study hard and I will pass the exam. b. If I do not study hard, then I will not pass the exam. c. I will pass the exam if and only if I study hard. 2. Let \(A\) = "The cat is black" and \(B\) = "The cat is fluffy." Determine the truth value of the following expressions, given that \(A\) is true and \(B\) is false. a. \(A \land B\) b. \(\neg A \lor B\) c. \(A \to B\) d. \(\neg (A \leftrightarrow B)\) 3. Complete the truth table for the following compound proposition: \((P \lor Q) \to \neg P\). | \(P\) | \(Q\) | \(P \lor Q\) | \(\neg P\) | \((P \lor Q) \to \neg P\) | | :---: | :---: | :---------: | :----: | :-----------------------: | | T | T | | | | | T | F | | | | | F | T | | | | | F | F | | | | ### Assignment 1. Construct a full truth table for the following propositions: a. \( (\neg P \land Q) \lor (P \to Q) \) b. \( \neg (P \leftrightarrow Q) \to (P \land \neg Q) \) 2. Consider the statement: "If the alarm rings (A) and it is morning (M), then I will wake up (W)." a. Write this statement in symbolic logic. b. Under what specific conditions (truth values of A, M, W) would this entire statement be false? c. If the alarm rings and it is morning, but you do not wake up, what can you say about the truth of the original statement? 3. Determine if the following two propositions are logically equivalent by constructing their truth tables and comparing the final columns: \( \neg (P \lor Q) \) and \( (\neg P \land \neg Q) \). ### Summary In this lesson, we explored the fundamental building blocks of propositional logic: logical constants or connectives. We learned about the five primary constants: Negation (\(\neg\)), Conjunction (\(\land\)), Disjunction (\(\lor\)), Conditional (\(\to\)), and Biconditional (\(\leftrightarrow\)). Each constant has a unique symbol, a specific meaning, and a defined truth table that dictates its truth value based on the truth values of the propositions it connects. We also practiced translating between English sentences and symbolic logic, and constructing truth tables for simple and compound propositions. Mastering these logical constants is essential for understanding and analyzing logical arguments and statements in various fields. ## Truth-Tables for negation, conjunction and disjunction ### Introduction Welcome to our lesson on truth tables! In logic, we often deal with statements that can be either true or false. These are called propositions. Sometimes, we combine these simple propositions to form more complex statements. To understand whether these complex statements are true or false, we use a powerful tool called a **truth table**. This lesson will introduce you to the basics of constructing and interpreting truth tables for three fundamental logical operations: negation, conjunction, and disjunction. ### Key Concepts #### What is a Proposition? A **proposition** is a declarative sentence that is either definitively true or definitively false, but cannot be both. It's a statement that has a truth value. * **Examples of Propositions:** * "The sky is blue." (True) * "2 + 2 = 5." (False) * "Nairobi is the capital of Kenya." (True) * **Non-examples of Propositions:** * "What time is it?" (A question) * "Close the door!" (A command) * "This statement is false." (A paradox - neither true nor false) #### What is a Truth Table? A **truth table** is a mathematical table used in logic to compute the functional values of logical expressions on each of their functional arguments, that is, on each combination of values taken by their logical variables. In simpler terms, it lists all possible truth values of a compound proposition for every possible combination of truth values of its simple propositions. #### Logical Operators (Connectives) Logical operators are symbols or words that connect propositions to form new, compound propositions. Each operator has a specific rule that determines the truth value of the compound proposition based on the truth values of the individual propositions. ##### Negation (NOT) * **Symbol:** * \[ \lnot \] (read as "not p" or "it is not the case that p") * **Meaning:** The negation of a proposition `p` reverses its truth value. If `p` is true, then \[ \lnot p \] is false. If `p` is false, then \[ \lnot p \] is true. * **Truth Table for Negation:** | p | \[ \lnot p \] | |---|-----| | T | F | | F | T | ##### Conjunction (AND) * **Symbol:** \[ \land \] (read as "p and q") * **Meaning:** The conjunction of two propositions `p` and `q` is true only if *both* `p` and `q` are true. If either `p` or `q` (or both) are false, then the conjunction is false. * **Truth Table for Conjunction:** | p | q | \[ p \land q \] | |---|---|----------| | T | T | T | | T | F | F | | F | T | F | | F | F | F | ##### Disjunction (OR) * **Symbol:** \[ \lor \] (read as "p or q") * **Meaning:** The disjunction of two propositions `p` and `q` is true if *at least one* of the propositions is true. It is only false if *both* `p` and `q` are false. This is known as inclusive OR. * **Truth Table for Disjunction:** | p | q | \[ p \lor q \] | |---|---|----------| | T | T | T | | T | F | T | | F | T | T | | F | F | F | ### Vocabulary * **Proposition:** A declarative sentence that is either true or false, but not both. * **Truth Value:** The state of a proposition being either true (T) or false (F). * **Compound Proposition:** A proposition formed by combining two or more simple propositions using logical operators. * **Logical Operator/Connective:** A symbol or word ( \[ \lnot \] , \[ \land \] , \[ \lor \] , etc.) that connects propositions. * **Negation ( \[ \lnot \] ):** The logical operation that reverses the truth value of a proposition. * **Conjunction ( \[ \land \] ):** The logical operation that yields true only if all propositions connected are true. * **Disjunction ( \[ \lor \] ):** The logical operation that yields true if at least one of the propositions connected is true. * **Truth Table:** A table showing all possible truth values of a compound proposition for every combination of its simple propositions. ### Examples Let's apply these concepts with some examples. #### Negation Example * Let `p` be the proposition: "The sun is a planet." (This is False, F) * \[ \lnot p \] : "The sun is not a planet." (This is True, T) * Let `q` be the proposition: "It is raining." (Assume this is True, T) * \[ \lnot q \] : "It is not raining." (This is False, F) #### Conjunction Example * Let `p` be: "2 is an even number." (True, T) * Let `q` be: "3 is an odd number." (True, T) * \[ p \land q \] : "2 is an even number AND 3 is an odd number." (True, T, because both are true). * Let `p` be: "Nairobi is in Egypt." (False, F) * Let `q` be: "Cairo is the capital of Egypt." (True, T) * \[ p \land q \] : "Nairobi is in Egypt AND Cairo is the capital of Egypt." (False, F, because `p` is false). #### Disjunction Example * Let `p` be: "I will go to the market." (Assume False, F) * Let `q` be: "I will cook dinner." (Assume True, T) * \[ p \lor q \] : "I will go to the market OR I will cook dinner." (True, T, because `q` is true). * Let `p` be: "The cat can fly." (False, F) * Let `q` be: "The dog can talk." (False, F) * \[ p \lor q \] : "The cat can fly OR the dog can talk." (False, F, because both `p` and `q` are false). ### Exercises Complete the following exercises to test your understanding. 1. **Complete the truth tables:** * **a) \[ \lnot (\lnot p) \] ** | p | \[ \lnot p \] | \[ \lnot (\lnot p) \] | |---|----------|------------------| | T | | | | F | | | * **b) \[ p \land (\lnot q) \] ** | p | q | \[ \lnot q \] | \[ p \land (\lnot q) \] | |---|---|----------|---------------------| | T | T | | | | T | F | | | | F | T | | | | F | F | | | * **c) \[ (\lnot p) \lor q \] ** | p | q | \[ \lnot p \] | \[ (\lnot p) \lor q \] | |---|---|----------|------------------| | T | T | | | | T | F | | | | F | T | | | | F | F | | | 2. **Determine the truth value of the following statements given:** * `p`: "Paris is the capital of France." (True) * `q`: "London is the capital of Germany." (False) * `r`: "2 is an even number." (True) * a) \[ \lnot p \] * b) \[ q \land r \] * c) \[ p \lor q \] * d) \[ (\lnot q) \lor (\lnot r) \] ### Assignment Continue practicing at home with these questions. 1. **Construct truth tables for the following compound propositions:** * a) \[ \lnot (p \lor q) \] * b) \[ (\lnot p) \land (\lnot q) \] 2. **Consider the following propositions and determine the truth value for each compound statement:** * `A`: "The sun rises in the east." (True) * `B`: "The moon is made of cheese." (False) * `C`: "Birds can fly." (True) * a) \[ A \land B \] * b) \[ \lnot C \] * c) \[ B \lor C \] * d) \[ (\lnot A) \land C \] ### Summary In this lesson, we explored the foundational concepts of truth tables and three essential logical operators: negation, conjunction, and disjunction. We learned that: * A **proposition** is a statement that is either true or false. * A **truth table** systematically lists all possible truth values for a compound proposition. * **Negation ( \[ \lnot \] )** reverses the truth value of a proposition. * **Conjunction ( \[ \land \] )** is true only when all connected propositions are true. * **Disjunction ( \[ \lor \] )** is false only when all connected propositions are false (it is true if at least one is true). Mastering these basic truth tables is crucial as they are the building blocks for understanding more complex logical statements and arguments in the future.