Block of Code

Practical Examples for Programmers

Propositional Logic

  1. Which of the following are true propositions, false propositions or not a proposition? (Hint: propositions can be true or false, but not both.)
    1. x + y = y + x for every pair of real numbers x and y. This is a true proposition. Note that x and y are defined as real numbers.
    2. All insects are ants. This is a false proposition. A bee is an insect, but not an ant.
    3. All ants are insects. This is a true proposition.
    4. 5 + 7 = 10. This is a false proposition.
    5. This statement is false. This is not a proposition because it could be true or false. We don’t know.
    6. What time is it? This is not a proposition. Questions can’t be propositions.
    7. Do not pass go. This is not a proposition.
    8. 2 + 3 = 5. This is a true proposition.
    9. x + 1 = 5 if x = 1. This is a false proposition.
  2. Determine which of the following is a proposition.
    1. x > 3. No because x is undefined.
    2. 2 > 3. Yes, this is a proposition (a false proposition).
    3. 2x + 11 = 23. No because x is undefined.
  3. For each of the following sentences, determine whether an “inclusive or” or an “exclusive or” is usually what is meant by the sentence. (Hint: “inclusive or” means one or both. “Exclusive or” means only one.)
    1. Lunch includes soup or salad. Exclusive.
    2. To enter the country you need a passport or a voter registration card. Inclusive.
    3. Publish or perish. Exclusive.
    4. Experience with C++ or Java is required. Inclusive.
  4. What is the value of x after each of the following statements is encountered in a computer program, if x = 3 before each statement is reached?
    1. if x < 8 then x := x + 1. Since 3 < 8, x = x + 1. Answer is 4.
    2. if (1 + 1 = 3) OR (8 > x) then x := x + 1. If false or true then x = x + 1. Answer is 4.
    3. if (2 + 3 = 5) AND (3 + 4 = 7) then x := x + 1. If true and true, x = x + 1. Answer is 4.
    4. if (1 + 1 = 2) XOR (x = 3) then x := x + 1. If exclusive true, then x = x + 1. Both can’t be true, so answer is 3.
  5. What is the value of x after each of the following statements is encountered in a computer program, if x = 6 before each statement is reached?
    1. if x < 3 then x := x + 1. False, so answer is 6.
    2. if (1 + 1 = 3) OR (3 > x) then x := x + 1. False or false, so answer is 6.
    3. if (2 + 3 = 5) AND (3 + 4 = 7) then x := x + 1. True and true, so answer is 7.
    4. if (1 + 1 = 2) XOR (x = 4) then x := x + 1. Only the first part of the conditional is true, therefore the whole conditional is true. Answer is 7.
  6. Evaluate each of the following expressions:
    1. 11000 AND (01011 OR 11011) = 11000 AND (11011) = 11000
    2. (01111 AND 10101) OR 01000 = 00101 OR 01000 = 01101
    3. (01010 XOR 11011) XOR 01000 = 10001 XOR 01000 = 11001
    4. (11011 OR 01010) AND (10001 OR 11011) = 11011 AND 11011 = 11011
  7. Fuzzy logic is used in artificial intelligence. In fuzzy logic, a proposition has a truth value that is a number between 0 and 1 inclusive. A proposition with a truth value of 0 is false, and one with a truth value of 1 is true. Truth values that are between 0 and 1 indicate varying degrees of truth. For instance, the truth value 0.75 can be assigned to the statement “Fred is happy” since Fred is happy most of the time, and the truth value 0.4 can be assigned to the statement “John is happy” since John is happy slightly less than half the time. The truth value of a proposition in fuzzy logic is the minimum of the truth value of the two propositions. What are the truth values of the statements:
    1. “Fred and John are happy.” Fred happy = .75 and John happy = .4. The truth value of a conjunction is the minimum. Answer is .4.
    2. “Neither Fred nor John is happy.” This can be looked at as the conjunction of Fred not happy and John not happy, because neither of them can be happy. Fred not happy = .25 and John not happy = .6. The truth value of a conjunction is the minimum. Answer is .25.
  8. Using the question above, suppose the truth value of .85 is assigned to the statement “Fred is happy” and the truth value of .35 is assigned to “John is happy”. What are the truth values of the following statements?
    1. “Fred and John are happy.” Fred happy = .85 and John happy = .35. The truth value of a conjunction is the minimum. Answer is .35.
    2. “Neither Fred not John is happy.” This can be looked at as the conjunction of Fred not happy and John not happy, because neither of them can be happy. Fred not happy = .15 and John not happy = .65. The truth value of a conjunction is the minimum. Answer is .15.
  9. Complete the following truth table by filling in the blanks with T or F as appropriate. Hint: remember that with a conditional (if p then q) if p is false then the proposition defaults to true because the test never happened.Truth Table 1-1
  10. Complete the following truth table by filling in the blanks with T or F as appropriateTruth Table 1-2
  11. Convert the following sentence into formal logic.
    John is smart and John is tall.
    Hint: The tilde (“~”) character is the same as the negation character in part A below. Both mean the same thing.
    p: John is smart
    q: John is tallTable 1-1