1
$\begingroup$

I'm having trouble representing these questions in a propositional logic formula:

Alice, Bob and Claire want to attend the CPS I lecture. The exercise groups are almost full, only group 1 and group 2 have places left.

(a) If Alice joins group 1, the tutor refuses to accept Bob because they always talk.

(b) At least one of Bob and Claire cannot go to group 1, as they lead a chess group together that meets at the same time.

(c) Claire hates Alice and doesn’t want to be in the same group.

(d) Alice wants to submit the solutions with either Bob or Claire and thus needs to be in a group with this person.

Model the above statements in propositional logic where the atomic propositions:

a(Alice), b (Bob), c (Claire) are assigned the value true if the corresponding person joins group 1, and false else.

Which persons join which group? Use a truth table to find out.

Here is my solution:

(a) a -> b

(b) ¬(b ^ c)

(c) a -> ¬c

(d) (a ^ b) xor (a ^ c)

I don't think the solutions are correct. What do you think what changes should I make?

How to find out which persons join which group using the truth table?

Thank you :)

$\endgroup$
  • $\begingroup$ I would write c) as $c\Rightarrow \neg a$. To build the truth table, you need to calculate values for each of the constraints and the final result will be the conjunction of all conditions. If the final result is true, that particular combination of values a, b, c is one of the solutions $\endgroup$ – Vasya Oct 25 '17 at 17:02
  • $\begingroup$ For (d) can it be a ^ (b v c)?. Also, (a) - (c) has 2 variables and (d) has 3 variables, how should I use the conjunction in this case? $\endgroup$ – Riya208 Oct 25 '17 at 19:30
  • $\begingroup$ I think you have the right constraint for d) (we get true only when a=1,b=1, c=0 or when a=1,b=0,c=1 but not when a=1,b=1, c=1). When you build the truth table, you'll have 8 columns: a, b,c, 4 constraints and the final result. Look for rows that have truth for all constraints, that will give you truth for the final result, all other rows will lead to false. Also, the first constraint should be a⇒¬b $\endgroup$ – Vasya Oct 25 '17 at 19:45
  • $\begingroup$ After thinking a bit, I believe you are right, it should be a ^ (b v c) for d), nothing prevents Claire to be in the same group with the other two. $\endgroup$ – Vasya Oct 25 '17 at 19:59
  • $\begingroup$ Regarding d) again: it should be (a ^ (b v c)) xor (¬a^(¬b v ¬c)) (it's ok for Alice to be in the second group as long as one of the other two is in the second group as well). Constraint c) should be c xor a. $\endgroup$ – Vasya Oct 25 '17 at 20:24
0
$\begingroup$

It looks like the only solution is this: Alice and Bob join the second group and Claire joins the first one.

$$ \begin{array}{c|c|c|c|c|c|c|c} a&b&c&a \Rightarrow \lnot b &\lnot (b \land c) &a \oplus c & (a \land(b\lor c))\oplus(\lnot a \land (\lnot b \lor \lnot c)) & f \\ F&F&F&T&T&F&T&F \\ F&F&T&T&T&T&T&T \\ F&T&F&T&T&F&T&F \\ F&T&T&T&F&T&F&F \\ T&F&F&T&T&T&F&F \\ T&F&T&T&T&F&T&F \\ T&T&F&F&F&T&T&F \\ T&T&T&F&F&F&T&F \\ \end{array} $$ As you can see, the only row that has truth for all conditions is the second one, i.e. Alice and Bob go to group 2 and Claire goes to group 1.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Yea, it makes sense. But, how to arrive at this solution using the truth table? $\endgroup$ – Riya208 Oct 25 '17 at 22:20
  • $\begingroup$ I edited the answer to include the truth table, the last column has conjunction of all four conditions $\endgroup$ – Vasya Oct 26 '17 at 1:16
  • $\begingroup$ Thanks a lot :) Now I see where did I go wrong. $\endgroup$ – Riya208 Oct 26 '17 at 8:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.