Skip to content Skip to navigation Skip to collection information

OpenStax-CNX

You are here: Home » Content » Intro to Logic » Exercises for Propositional Logic I

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • Rice Digital Scholarship

    This collection is included in aLens by: Digital Scholarship at Rice University

    Click the "Rice Digital Scholarship" link to see all content affiliated with them.

Recently Viewed

This feature requires Javascript to be enabled.
 

Exercises for Propositional Logic I

Module by: Ian Barland, John Greiner, Phokion Kolaitis, Moshe Vardi, Matthias Felleisen. E-mail the authors

Summary: Problems on propositional logic, including truth-tables, boolean algebra, and inference rules.

Please write logic formulas using the syntax previously defined, using false (or for brevity, “F”), true (or “T”), ¬, ∧, ∨, and ⇒. Except where directed, use only these connectives.

Aside:

You can download WaterWorld if you like. At Rice University, WaterWorld is installed on OwlNet, in /home/comp280/bin/waterworld.

Propositional Logic

Exercise 1

[Practice problemsolution provided.]

Your friend Tracy argues: “ It is bad to be depressed. Watching the news makes me feel depressed. Thus, it's good to avoid watching the news. ”

Regardless of whether the premises and conclusion are true, show that the argument is not, by showing it doesn't hold for all domains. Replace “depressed” and “watching news” with expressions which leave the premises true, but the conclusion false (or at least, what most reasonable people would consider false).

Solution

Lots of possible counterexamples. “ It is bad to be depressed. Doing homework makes me depressed; so it's good to not do my homework. ” Or, “ It is bad for people to be in physical pain. Childbirth causes pain. Therefore childbirth needs be avoided by all people. ” If the original conclusion is really correct, Tracy needs to elucidate some of his unspoken assumptions.

The flaw seems to be along the lines of, “ avoiding bad in the short run may not always be good in the long run ” (or equivalently, sometimes you have to choose the lesser of two evils). No, you weren't asked to name a specific flaw, and reasonable people can differ on precisely what the flaw is. (And, formal logic is not particularly helpful here.) Nonetheless, uncovering hidden assumptions in arguments often helps understand the real issues involved.

Aside:
For fun, pick up the front page of the daily newspaper, and see how many arguments use faulty rules of inference and/or rely on unspoken premises (which not all might agree with). In particular, political issues as spun to the mainstream press are often riddled with error, even though there are usually reasonable arguments on both sides which policy-makers and courts debate.

Exercise 2

[Practice problemsolution provided.]

An acquaintance says the following to you: “ Chris claims knowledge is more important than grades. But she spent yesterday doing an extra-credit assignment which she already knew how to do. Therefore, she's a hypocrite and deserves no respect. ”

Regardless of whether the premises and conclusion are true, show that the argument is not, by showing it doesn't hold for all domains. Replace “knowledge” and “grades” with expressions which give you true premises, but a false conclusion (or at least, what most reasonable people would consider false).

Note:

Exaggerate “knowledge” to something more important, and “grades” to something less important.

Solution

“ Terry claims that encouraging human-rights is more important than playing Tetris. But Terry played Tetris yesterday rather than volunteering with Amnesty International. ” Most people wouldn't condemn Terry as a hypocrite just because of this; even the most dedicated of people are entitled to some free time. If your friend wants to prove Terry hypocritical, they'll have to provide further evidence or arguments.

Or similarly, “ Politician X claims to support science funding, but voted against a proposal to shift all Medicare funds to NASA. ”

Exercise 3

[Practice problemsolution provided.]

While the following argument may sound plausible initially, give a particular situation where the conclusion doesn't hold (even though the premises do). Then, in a sentence or two, sketch why your counterexample may still represent rational behavior by pointing out a real-world subtlety that the initial argument ignored.

  1. If a certain outfit meets a dress code, then per force all less-revealing outfits also meet that dress code.

  2. In public transportation projects, out of two alternatives, the cheaper one which gets the job done is the better choice.

Solution

  1. It can be socially acceptable to wear my swimsuit into a fast-food restaurant. My underwear is less revealing than my swimsuit, and yet it would still raise many more eyebrows to go to that restaurant in my underwear, than my swimsuit.

    Clothes (and style in general) somehow encompass a form of communication, and people may object to an outfit's mood or message without actually objecting to how much the outfit reveals. (Other examples of communication-through-style include team logos, t-shirts with humorous slogans, and arm bands.)

  2. Buses are a lot cheaper than light rail. Yet, the light-rail here in Houston demonstrates that many people who wouldn't routinely take a bus are willing to take light rail. (Only after we recognize this, can we try to figure out what why the difference exists, and then brainstorm to find a better overall solution.)

Exercise 4

Choose just one of the following informal arguments. While the argument sounds plausible initially, give a particular situation where the conclusion doesn't hold (even though the premises do). Then, briefly state why your counterexample may still represent rational behavior by pointing out a real-world subtlety that the initial argument ignored.

  1. [cell phone] Talking on a cell phone while driving increases the likelihood of an accident. Interestingly, hands-free phones do not significantly help. It's just the distraction of a phone conversation that causes the problem.

  2. [equivalent products] If two companies offer two materially equivalent products, then most everybody will buy the cheaper one.

  3. [service] In a free market, if a company doesn't offer good service, individual customers will become fed up and take their business elsewhere.

  4. [web browser] If there are two versions of a free web browser, and they run equally quickly, users will use the one with better features/interface.

  5. [door-locking] Anybody who really wants to break into your house while you're gone will be able to. (For instance, using a towel to muffle sound, break the corner of a back window, reach in and unlatch the window, and climb through.) So there's no point in locking your front door.

Exercise 5

[Practice problemsolution provided.]

Let pp, qq, and rr be the following propositions:

  • pp: You get an A on the final exam
  • qq: You do every exercise in the book.
  • rr: You get an A in this class.
Write the following formulas using pp, qq, and rr and logical connectives.

  1. You get an A in this class, but you do not do every exercise in the book.

  2. To get an A in this class, it is necessary for you to get an A on the final.

  3. Getting an A on the final and doing every exercise in the book is sufficient for getting an A in this class.

Solution

  1. r¬qr q

  2. rpr p

    Think of the English being reworded to “ If you got an A in this class, you must have gotten an A on the final. ”

  3. pqr p q r

Exercise 6

Translate the following English sentences into propositional logic. Your answers should be WFFs.

  1. If the Astros win the series (AWAW), then pigs will fly (PFPF).

  2. Pigs will not fly, and/or bacon will be free (BFBF).

  3. The Astros will win the series, or bacon will be free, but not both.

Exercise 7

[Practice problemsolution provided.]

It just so happens that all the web pages in Logiconia which contain the word “Poppins” also contain the word “Mary”. Write a formula (a query) expressing this. Use the proposition PoppinsPoppins to represent the concept “the web page contains 'Poppins'” (and similar for MaryMary).

Solution

PoppinsMary Poppins Mary

Exercise 8

  • If a Logicanian page contains the word “weasel”, then it also contains either “words” or “eyed”; and
  • Whenever a Logiconian page contains the word “mongoose”, it does not also contain the word “weasel”; and
  • Finally, all Logiconian pages contain the word “Logiconia”, rather patriotically.

Write a formula expressing all this. (Your formula will involve five propositions: weaselweasel, wordswords, … Try to find a formula which mirrors the wording of the English above.)

Given the above statements, if a web page in Logiconia does not contain “weasel”, does it contain “mongoose”?

Let's go meta for a moment: Is this web page Logiconian? (Yes, this one you're looking at now, the one with the homework problems.) Explain why or why not.

Exercise 9

Different search engines on the web have their own syntax for specifying searches.

Aside:

Note that a formula may be true for some web pages, and false for others. The search engine is concerned with finding all web pages which satisfy the formula. This is called a query, in database lingo.
Only a few allow full Boolean queries. Some interpret a list of several words in a row as an implicit conjunction, others as an implicit disjunctions.

  1. Read about the search syntax for the search language of eBay®. Write an eBay query for auctions which contain “border”, do not contain “common”, and contain at least one of “foreign” or “foriegn” [sic, misspellings are a great way to find underexposed auctions].

  2. Google£'s advanced search is typical for the online search engines. In particular, you can search for results containing all of aa, bb, …, at least one of cc, dd, …, and none of ee, ff, …. Describe how that corresponds to a Boolean formula.

  3. Give an example of a Boolean formula which cannot be rewritten to conform to Google's advanced search interface.

Exercise 10

[Practice problemsolution provided.]

Figure 1: A sample WaterWorld board
Figure 1 (hwA-1.png)

Consider the particular board shown in the above figure.

  1. Y-safeY-safe, Y-has-0Y-has-0, and ¬Y-has-2Y-has-2 are among the formulas which are true for this board but not for all boards. That is, they are neither domain axioms nor tautologies. Give two other such formulas.

  2. V-safeV-safe might or might not be true for this board. Give two other such formulas.

Solution

  1. There are many simple answers, such as Y-has-1Y-has-1, ¬W-has-1W-has-1, …

  2. There are many simple answers, such as aa, N-has-1N-has-1, J-has-3J-has-3, …

For each, there are also many such formulas composed with connectives such as ∧ and ∨.

Exercise 11

In that same board, is location WW safe? What is your informal reasoning? (List all your small steps.) Similarly for location PP.

Exercise 12

Give a domain axiom of WaterWorld which was omitted in the ellipses in the WaterWorld domain axioms.

Exercise 13

Even allowing for ellision, the list of WaterWorld domain axioms is incomplete, in a sense. The game reports how many pirates exist in total, but that global information is not reflected in the propositions or axioms.

First, assume we only use the default WaterWorld board size and number of pirates, i.e., five. Give samples of the additional axioms that we need.

Next, generalize your answer to model the program's ability to play the game with a different number of pirates.

Exercise 14

Give one WFF which meets all three conditions:

  • true in all WaterWorld boards (“A theorem of WaterWorld”)
  • not already listed as one of the WaterWorld domain axioms, and
  • not a tautology of propositional logic (can be made false in some truth assignment, though it may not be a truth assignment which satisfies the waterworld axioms).

Reasoning with Truth Tables

When writing truth tables, please list rows in the order used in all examples: FF, FT, TF, TT. For three-input tables, use the above four lines preceded by F, then the above four lines preceded by T.

Exercise 15

In a truth table for two inputs, provide a column for each of the sixteen possible distinct functions. Give a small formula for each of these functions.

Note:

These functions will include those for ∧, ∨, and the other connectives whose truth tables you've already seen.

Exercise 16

[Practice problemsolution provided.]

Write the truth table for xnor, the negation of exclusive-or, What is a more common name for this Boolean function?

Solution

Table 1: Truth table for xnor
φφ ψψ φxnorψ xnor xnor φ ψ
false false true
false true false
true false false
true true true

This is the “equals” for Booleans. It is also represented by the connective if-and-only-if.

If you said something like “the both-or-neither function”, that's not quite good enough, as it's a roundabout way of expressing the simple idea of equivalence. Granted, it takes some practice to internalize Booleans as values, and that equality is as valid for them as for any other value.

Exercise 17

How many years would it take to build a truth table for a formula with 1000 propositions? Assume it takes 1 nanosecond to evaluate each formula.

A formula with 1000 propositions clearly isn't something you would create by hand. However, such formulas easily arise when modeling the behavior of a program with a 1000-element data structure.

Exercise 18

Use truth tables to answer each of the following. Showing whether the connectives obey such properties via truth tables is one way of establishing which equivalences or inference rules we should use.

  1. Show whether ⇒ is commutative.

  2. Show whether ⊕ is commutative.

  3. Show whether ⊕ is associative.

  4. Prove that ∧ distributes over ∨: φ(ψθ)φψφθ φ ψ θ φ ψ φ θ

    Note:

    This version is left-distributivity. Right-distributivity follows from this plus the commutativity of ∧.
  5. Prove that ∨ distributes over ∧: φψθ(φψ)(φθ) φ ψ θ φ ψ φ θ

  6. Show whether ∧ or ∨ distribute over ⇒.

  7. Show whether ⇒ distributes over ∧ or ∨.

  8. Show whether ∧ or ∨ distribute over ⊕.

  9. Show whether ⊕ distributes over ∧ or ∨.

Exercise 19

For each of the following, find a satisfying truth assignment, (values of the propositions which make the formula true), if any exists.

  1. (a¬b)a a b a
  2. (ac¬b)(ab) a c b a b

Exercise 20

For each of the following, find a falsifying truth assignment, (values of the propositions which make the formula false), if any exists.

  1. (a¬b)a a b a
  2. (¬b(ac))ab b a c a b

Exercise 21

Formula φφ is stronger than formula ψψ if ψψ is true whenever φφ is true (i.e., φφ is at least a strong as ψψ), but not conversely. Equivalently, this means that φψ φ ψ is always true, but ψφ ψ φ is not always true.

As one important use of this concept, if we know that ψθ ψ θ , and that φφ is stronger than ψψ, then we also know that φθ φ θ . That holds simply by transitivity. Another important use, which is outside the scope of this module, is the idea of strengthening an inductive hypothesis.

Similarly, φφ is weaker than formula ψψ whenever ψψ is stronger than φφ.

Show which of the following hold. When true, show φψ φ ψ is true by a truth table, and show a falsifying truth assignment for ψφ ψ φ . When false, give a truth table and truth assignment the other way around.

  1. aba b is stronger than aba b.

  2. aba b is stronger than aa.

  3. aa is stronger than aba b.

  4. bb is stronger than aba b.

Exercise 22

Using truth tables, show that (ac)(bc)(ca) a c b c c a is equivalent to (bc)a b c a . but not equivalent to (ac)(bc) a c b c .

Exercise 23

[Practice problemsolution provided.]

When writing a complicated conditional that involves multiple pieces of data, it is easy to incorrectly oversimplify. One strategy for avoid mistakes is to write such code in a two-step process. First, write a conditional with a case for every possible combination, as in a truth table. Second, simplify the conditional.

Using this approach, we might obtain the following code after the first step. Simplify this code.


list merge_sorted_lists(list list1, list list2)
{
   if (is_empty(list1) && is_empty(list2))
      return empty_list;
   else if (is_empty(list1) && !is_empty(list2))
      return list2;
   else if (!is_empty(list1) && is_empty(list2))
      return list1;
   else if (!is_empty(list1) && !is_empty(list2)) {
      if (first_element(list1) < first_element(list2))
         return make_list(first_element(list1),
                          merge_sorted_lists(rest_elements(list1),list2));
      else if (first_element(list1) >= first_element(list2))
         return make_list(first_element(list2),
                          merge_sorted_lists(list1,rest_elements(list2)));
   }
}
    

Solution


list merge_sorted_lists(list list1, list list2)
{
   if (is_empty(list1))
      return list2;
   else if (is_empty(list2))
      return list1;
   else {
      if (first_element(list1) < first_element(list2))
         return make_list(first_element(list1),
                          merge_sorted_lists(rest_elements(list1),list2));
      else
         return make_list(first_element(list2),
                          merge_sorted_lists(list1,rest_elements(list2)));
   }
}
    

Alternatively, we could test the emptiness of the lists in the other order.

Exercise 24

Consider the following conditional code, which returns a boolean value.


int  i;
bool a,b;

…

if (a && (i > 0))
   return b;
else if (a && i <= 0)
   return false;
else if (a || b)
   return a;
else
   return (i > 0);
    

Simplify it by filling in the following blank with a single Boolean expression. Do not use a conditional (such as if or ?:).


int  i;
bool a,b;

…

return ________________;
    

Use either Java/C++ or Scheme syntax. In the former case, please fully parenthesize to make your formula unambiguous, rather than relying on Java's or C++'s many levels of operator precedence.

Reasoning with Equivalences

Exercise 25

[Practice problemsolution provided.]

Using algebraic identities, and the definition or nor (mnemonic: “not or”), written , φψ¬(φψ) φψ φ ψ , express the function ∧ in terms of only. That is, give a formula which doesn't use ∧, ∨, ¬, but instead only uses and which has the same truth table as φψφψ.

Solution

First we show that we can write negation in terms of , or more specifically, ¬θθθ θ θ θ . Checking this on a truth table is pretty easy (there are only two rows to check). But for this question we need to use algebraic manipulation. This can be derived in a couple of simple steps:

Table 2
1¬θθ 
2¬θ¬θ θ θ Idempotency of ∧
3¬(θθ)θ θ DeMorgan's law
4θθθ θ Definition of nor

We use this lemma to show our ultimate goal:

Table 3
1δεδ ε 
2¬¬(δε)δ ε Double Complementation
3¬(¬δ¬ε)δ ε DeMorgan's law
4¬((δδ)¬ε) δ δ ε Lemma, with [θδ][θδ]
5¬((δδ)(εε)) δ δ ε ε Lemma, with θ=εθ ε
6δδεε δ δ ε ε Definition of nor, where φ=δδ φ δ δ , and ψ=εε ψ ε ε

Note that we judiciously used new meta-variables δδ and εε rather than re-using φφ and ψψ (which would still be correct, but would make the graders need to pay much closer attention to the scope of those variables).

Exercise 26

Similar to the previous exercise, express each of the following using nand only, and prove correctness using the algebraic identities.

This operation is particularly interesting, since making a NAND gate in hardware requires only two transistors.

  1. ¬

Exercise 27

Using algebraic identities, show that (ac)(bc)(ca) a c b c c a is equivalent to (bc)a b c a .

This is an algebraic hand-evaluation: a series of formulas joined by . Don't write just portions of previous formulas and mysteriously re-introduce the dropped parts later. For each step, mention which identity you used. It is also helpful if you underline the formula you are rewriting in the next step. You can use commutativity and associativity without using a separate line, but mention when you use it.

Exercise 28

In two exercises, you've shown the same equivalence by truth tables and by algebraic identities.

  1. What is an advantage of using truth tables? What is an advantage of using identities?

  2. In that truth table exercise, you also showed two formulas φφ and ψψ non-equivalent. It is also possible to do so with Boolean algebra rather than truth tables. How?

  3. Describe a hybrid approach, combining truth tables and Boolean algebra, to prove the equivalence and non-equivalence of formulas.

  4. To ponder on your own without turning it in: Which approach appeals more to you?

Exercise 29

Using algebraic identities, rewrite the formula (abc)¬b a b c b to one with fewer connectives.

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks