Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.3k answers

1.7k comments

556 users

+1 vote

Given boolean variables x1, x2, and x3, construct a propositional formula φ that 

holds if and only if an odd number of the variables is true. 

DNF: (x3 x2 x1) (x3 ¬x2 ¬x1) (¬x3 x2 ¬x1) (¬x3 ¬x2 x1) 

In another Question:

Given boolean variables x1, x2, x3, and x4, construct a propositional formula φ 

that holds if and only if an even number of the variables is true. 

DNF:

(x4 x3 x2 x1) (x4 x3 ¬x2 ¬x1)
(x4 ¬x3 x2 ¬x1) (x4 ¬x3 ¬x2 x1) (¬x4 x3 x2 ¬x1) (¬x4 x3 ¬x2 x1) (¬x4 ¬x3 x2 x1) (¬x4 ¬x3 ¬x2 ¬x1) 

Why we are taking this (¬x4 ¬x3 ¬x2 ¬x1) 

As far as I understand if x1=x2=x3=x4=0 it should be false?

Correct me please.

Reference papers 2015

in # Study-Organisation (Master) by (190 points)

1 Answer

+1 vote
We add the minterm (¬x4 ∧ ¬x3 ∧ ¬x2 ∧ ¬x1) since that is the variable assignment that makes all variables false, i.e., 0 are true, and 0 is an even number. The formulas are however easier expressed as 1⊕x1⊕x2⊕x3⊕x4 (for an even number of variables) and x1⊕x2⊕x3⊕x4 (for an odd number of variables).
by (170k points)
Then for this question Given boolean variables x1, x2, and x3, construct a propositional formula φ that
holds if and only if an odd number of the variables is true. why we are not taking midterm? (!x3 ∧ !x2 ∧ !x1) odd number of 0 are true?

DNF: (x3 ∧ x2 ∧ x1) ∨ (x3 ∧ ¬x2 ∧ ¬x1) ∨ (¬x3 ∧ x2 ∧ ¬x1) ∨ (¬x3 ∧ ¬x2 ∧ x1)
Well, since there are 0 variables true, and 0 is an even number. Look at the truth table of the function that we are interested in:

---------------------
x3    x2    x1    ??
---------------------
0    0    0    0
0    0    1    1
0    1    0    1
0    1    1    0
1    0    0    1
1    0    1    0
1    1    0    0
1    1    1    1
---------------------

DNF x3&x2&x1 | x3&!x2&!x1 | !x3&x2&!x1 | !x3&!x2&x1
RMF x1⊕x2⊕x3

Related questions

0 votes
1 answer
0 votes
2 answers
0 votes
1 answer
0 votes
1 answer
Imprint | Privacy Policy
...