Find a compound proposition involving propositional variables a , b , c , and d that is true precisely when at least two of a , b , c , and d are true.

Question

Explain in one or two sentences how you got your compound proposition and why your answer works.

Answer 1

There are definitely more-elegant solutions than the following, but I'd rather give a suggestion that's accessible as you're working to get this introductory comfort with the field, so let's go super-literal and just list all the pairings we care about... first in English!

We want something which will evaluate to true if any of the following conditions are met:

1. a and b are true, or
2. a and c are true, or
3. a and d are true, or
4. b and c are true, or
5. b and d are true, or
6. c and d are true

Notice how I systematically created a list by starting with the first two variables and running the second through all other possibilities before advancing the first variable to the next possibility and repeating.

(another discrete math tip from a different unit: you can double-check you have the right number of pairings by considering that with 4 variables of which you want to choose 2 distinct ones, you're looking for ₄C₂ = 6 items on the list!)

We're nearly there at this point, we can just translate the statement from English into Propositional Logic, paying attention to grouping: the individual bullet points are a grouping mechanism in our listing, so we should use parentheses to keep them grouped as we link the pairs of "and"s (∧) together by the "or"s (∨).

Our final statement looks like this, see if you can trace out how it's saying the same thing:

(a∧b)∨(a∧c)∨(a∧d)∨(b∧c)∨(b∧d)∨(c∧d)

Since each of the smaller statements is true precisely when at least the two specific variables mentioned in that part are true, once we list all of them we'll have all our possibilities for how any two different things can be true. And since we haven't added anything that rules out more than two being true (note a∧b's evaluation has nothing to do with the values of c and d), we really do have all ways of having at least two of a, b, c, and d be true.

I hope that helps!