Who can enter?

Logic Level 4

A particular establishment has a very strict but twisted rule by which people are allowed to enter their premises. The following are allowed to enter:

  1. those who are 18 and above and have firearms, wearing sleeveless tops and slippers;
  2. those who aren't 18 and above and don't have firearms, wearing neither sleeveless tops nor slippers;
  3. those who aren't 18 and above and have firearms, wearing neither sleeveless tops nor slippers;
  4. those who aren't 18 and above and have firearms, wearing sleeveless tops and slippers;
  5. those who are 18 and above and have firearms, wearing slippers but not sleeveless tops;
  6. those who aren't 18 and above and don't have firearms, wearing slippers but not sleeveless tops;
  7. those who aren't 18 and above and have firearms, wearing slippers but not sleeveless tops.

If a person satisfies any of these seven rules, they are allowed to enter.

However, people don't even read these rules as they are too much to read for anyone. We can simplify these seven rules further into a fewer number of rules.

What is the least number of rules that these can be rewritten into, such that, again, any person satisfying any of the resulting rules is allowed to enter?


Note: Each rule you write must be a conjunction of two of the four conditions "18 or above," "have firearms," "wearing sleeveless tops," and "wearing slippers," or their respective negations. Thus, for example, a rule like "those who wear slippers or sleeveless tops" is not valid because it's a disjunction.

4 1 5 3 6 7 2

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Efren Medallo
May 26, 2017

The problem looks for the most efficient ruling to satisfy all the given conditions allowing the entry of the people to the said establishment. Note that we have four binary conditions (Having firearms, Being 18 and above, Wearing sleeveless tops, Wearing slippers). If we treat these as boolean variables, we can construct a very efficient truth function for that consisting of the least number of disjunct minterms (or products of absolute conditions). We will construct a K K -map to do that.

We first label these conditions A A , B B , C C , D D .

A A = Having an age of 18 18 and above

B B = Possession of firearms

C C = Wearing a sleeveless top

D D = Wearing slippers

Now we have the combinations of A B AB as the columns, and those of C D CD as the rows.

C D A B 00 01 11 10 00 01 11 10 \begin{array}{|c|c|c|c|c|} \hline \ \ CD|AB \ \ &\ \ 00\ \ &\ \ 01\ \ &\ \ 11\ \ &\ \ 10\ \ \\ \hline \hline \ \ 00\ \ &\ \ \ \ &\ \ \ \ &\ \ \ \ &\ \ \ \ \\ \hline \ \ 01\ \ &\ \ \ \ &\ \ \ \ &\ \ \ \ &\ \ \ \ \\ \hline \ \ 11\ \ &\ \ \ \ &\ \ \ \ &\ \ \ \ &\ \ \ \ \\ \hline \ \ 10\ \ &\ \ \ \ &\ \ \ \ &\ \ \ \ &\ \ \ \ \\ \hline \end{array}

Now, we place those 7 7 conditions here, and see whether it simplifies to a more condensed ruling.

Condition 1: Those who are 18 and above ( A A ) that have firearms ( B B ), but are wearing sleeveless tops ( C C ) and slippers ( D D ).

So we put a 1 1 on where A B C D ABCD is.

C D A B 00 01 11 10 00 01 11 1 10 \begin{array}{|c|c|c|c|c|} \hline \ \ CD|AB \ \ &\ \ 00\ \ &\ \ 01\ \ &\ \ 11\ \ &\ \ 10\ \ \\ \hline \hline \ \ 00\ \ &\ \ \ \ &\ \ \ \ &\ \ \ \ &\ \ \ \ \\ \hline \ \ 01\ \ &\ \ \ \ &\ \ \ \ &\ \ \ \ &\ \ \ \ \\ \hline \ \ 11\ \ &\ \ \ \ &\ \ \ \ &\ \ 1\ \ &\ \ \ \ \\ \hline \hline \ \ 10\ \ &\ \ \ \ &\ \ \ \ &\ \ \ \ &\ \ \ \ \\ \hline \end{array}

Well, fill this in for the rest, and we will get

C D A B 00 01 11 10 00 1 1 01 1 1 1 11 1 1 10 \begin{array}{|c|c|c|c|c|} \hline \ \ CD|AB \ \ &\ \ 00\ \ &\ \ 01\ \ &\ \ 11\ \ &\ \ 10\ \ \\ \hline \hline \ \ 00\ \ &\ \ 1\ \ &\ \ 1\ \ &\ \ \ \ &\ \ \ \ \\ \hline \ \ 01\ \ &\ \ 1\ \ &\ \ 1\ \ &\ \ 1\ \ &\ \ \ \ \\ \hline \ \ 11\ \ &\ \ \ \ &\ \ 1\ \ &\ \ 1\ \ &\ \ \ \ \\ \hline \hline \ \ 10\ \ &\ \ \ \ &\ \ \ \ &\ \ \ \ &\ \ \ \ \\ \hline \end{array}

Note that there are two squares of 2 units per side. This means that we can condense the seven rules into two disjunct rules.

For the first square closest to the edge, note the that for all four instances, { A B C D , A B C D , A B C D , A B C D } \{ A'B'C'D', A'BC'D', A'B'C'D, A'BC'D \} , it is always true that A = 0 A=0 and C = 0 C=0 , or that A C A'C' .

For the other square, a similar reasoning would lead us to B D BD .

So, the condensed truth function for the ruling of entry to the establishment is

f ( A , B , C , D ) = A C + B D f( A,B,C,D) = A'C' + BD

meaning that there are only two disjunct rules. These are the ones who are allowed to enter.

  1. Those who are not 18 18 and above and don't wear sleeveless tops.

  2. Those who have firearms and wear slippers.

But you could concatenate that into: Those who are under 18 and don't wear sleeveless tops, or those who have firearms and wear slippers. Technically, this is still only 1 rule.

Siva Budaraju - 4 years ago

Log in to reply

you used or

Razzi Masroor - 4 years ago

Log in to reply

So? The problem never said anything against using "or".

Siva Budaraju - 4 years ago

Log in to reply

@Siva Budaraju One must satisfy ALL conditions in the rule for it to be true. Since an or nullifies that said statement, as it only requires at least just one of the conditions to be true, concatenating that will mean "Those who are aged under 18 and don't wear sleeveless tops, AND have firearms and wear slippers." Which isn't the case. Remember that each rule must satisfy this: "All conditions set in any rule must be TRUE for the rule to be TRUE.

Efren Medallo - 4 years ago

Log in to reply

@Efren Medallo That is not true. Since it is ONE statement; it can be seen as ONE condition.

Siva Budaraju - 4 years ago

Log in to reply

@Siva Budaraju No, I'm not pertaining to the truth of the statement. I am saying that as per written in the problem details and assumptions, disjunctions in any rule is not allowed. That is why OR statements cannot be considered as a single statement.

Efren Medallo - 4 years ago

Log in to reply

@Efren Medallo Simply put, the statement "all conditions inside any rule must be true for the rule to be true" implies that all the conditions must be logically bound by conjunction, and conjunction alone.

Efren Medallo - 4 years ago

Log in to reply

@Efren Medallo But why can't I define "Those who are under 18 and don't wear sleeveless tops, or those who have firearms and wear slippers" to be one condition?

Siva Budaraju - 4 years ago

Log in to reply

@Siva Budaraju Because that is a disjunction.

Efren Medallo - 4 years ago

I have clarified the statement of the problem. Essentially it's a problem of simplifying a DNF formula into an equivalent DNF formula.

Ivan Koswara - 4 years ago

Log in to reply

Ok... Now the problem is correct.

Siva Budaraju - 4 years ago

Log in to reply

@Siva Budaraju When I saw the problem, I saw the details and clarifications part having that important information. I'm not sure if it's edited in before or after your attempt; if you attempted the problem before the details and clarifications part was there, you can claim your answer was correct to the problem you solved.

Ivan Koswara - 4 years ago

Log in to reply

@Ivan Koswara The note at the bottom wasn't there when I solved it.

Siva Budaraju - 4 years ago

Log in to reply

@Siva Budaraju You can report the problem so an admin can see and check. Like other problems; you can also report them if you think your answer should be correct.

Ivan Koswara - 4 years ago

Log in to reply

@Ivan Koswara Ehh.. It's ok. It's only one problem anyway, and it is corrected now.

Siva Budaraju - 4 years ago

Are you able to explain how a rule can still be condensed once it has already been rewritten into another condensed form?

I.e. Once { A B C D , A B C D , A B C D , A B C D } \{ A'B'C'D', A'BC'D', A'B'C'D, A'BC'D \} has been rewritten to be A C A'C' , why aren't we left with the table below?

C D A B 00 01 11 10 00 01 1 11 1 1 10 \begin{array}{|c|c|c|c|c|} \hline \ \ CD|AB \ \ &\ \ 00\ \ &\ \ 01\ \ &\ \ 11\ \ &\ \ 10\ \ \\ \hline \hline \ \ 00\ \ &\ \ \ \ &\ \ \ \ &\ \ \ \ &\ \ \ \ \\ \hline \ \ 01\ \ &\ \ \ \ &\ \ \ \ &\ \ 1\ \ &\ \ \ \ \\ \hline \ \ 11\ \ &\ \ \ \ &\ \ 1\ \ &\ \ 1\ \ &\ \ \ \ \\ \hline \hline \ \ 10\ \ &\ \ \ \ &\ \ \ \ &\ \ \ \ &\ \ \ \ \\ \hline \end{array}

Jonathan Quarrie - 4 years ago

Log in to reply

That is because that would result into having at most 4 4 disjunct rules. Simplification of boolean expressions always starts at looking for the largest possible groups. However, even if a single expression has already been accounted for, it may still be reused for as long as it further simplifies other boolean expressions. There's no stopping us into reusing expressions which have been used in concatenating other expressions. For better understanding, please read this .

Efren Medallo - 4 years ago

Log in to reply

That's very useful. Thank you!

Jonathan Quarrie - 4 years ago

Wow, using a Karnaugh map to solve this question, genius! :)

Krishna Deb - 3 years, 12 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...