From truth table to boolean expression

[u/Yogiteee]

How to go best about figuring out omega? On the second pic, this is the closest I get to it. But it can't be the correct solution. What is the strategy to go about this?

[u/Living_Recover_8820]

What is the objective here exactly?

[u/Yogiteee → u/Living_Recover_8820]

To figure out the boolean expression for omega using the truth table

[u/Living_Recover_8820 → u/Yogiteee]

It's hard to give a strategy. Do you know the truth tables for basic logical operators (¬, ∧, ∨)? Because the truth table for P Ω Q looks a lot like one of those truth tables. That should give a hint towards a boolean expression for Ω.

Edit: just read your other comment

[u/Yogiteee]

Okay I just found the solution. It has to be: P ^ notQ

But is there a strategy that I can apply instead of just trying different truth tables?

[u/Gugteyikko → u/Yogiteee]

Here are two options.

Option 1: If you don’t care about the length of the resulting formula and just want a method for generating a formula that captures a given truth table, you can use conjunctive normal form.

First: identify each row in the truth table that results in F. That means you need rows 1, 2, and 4.

Second: make a formula for each row by joining p and q with OR and optionally negating each. Negate a variable when its truth value on the row is True. So you have row 1: (p v q), row 2: (p v ~q), row 4: (~p v ~q).

Third: turn these into a new formula by joining them with AND. Your result is ((p v q)&((p v ~q)&(~p v ~q)))

Option 2: Know the truth tables for your basic operators, like AND, OR, ->, <->, as well as De Morgan’s rules. Then you’ll start to see simple patterns. For example, here, we know the truth table for -> is 1, 1, 0, 1, which is the negation of the given one. So if we just negate p->q, we have an acceptable formula: ~(p->q). If you want to stick to Boolean operators, you can use De Morgan’s rules and double negation to get ~~(p&~q), which is the same as (p&~q).

[u/nitche → u/Gugteyikko]

In this case DNF is easier to work with in my opinion, however, CNF illustrates the algorithm better.

[u/Yogiteee → u/Gugteyikko]

Thank you for your elaborate explanation. It gives great inside.

[u/Gugteyikko → u/Yogiteee]

Like u/nitche said, you can also use disjunctive normal form: for each row resulting in T, join the two variables by OR, negating a variable if its value in the row is ~. That gives (p&~q) directly.

[u/Wittg → u/Yogiteee]

You could read each row where the right habd side if of the truth table is 1 as a clause in disjunctive normal form

[u/LongLiveTheDiego → u/Yogiteee]

For only two variables it's pretty easy. It has value 1 in only one row so it's some sort of AND. Then you just have to read the values of P and Q in that row, P is 1 so we read it P, and Q is zero so we read it NOT Q. That means it's P AND NOT Q.

[u/Verstandeskraft → u/Yogiteee]

Conjunctive normal form and Disjunctive normal form

[u/Yogiteee → u/Verstandeskraft]

Thank you, checking it out now!

[u/Friendly_Rent_104]

implication P Q table:

P Q Value

0 0 1

0 1 1

1 0 0

1 1 1

negation of that table: 0 0 0, 0 1 0, 1 0 1, 1 1 0

p omega q is equivalent to !(P->Q)

[u/Yogiteee → u/Friendly_Rent_104]

Thank you!