All Questions
Tagged with propositional-calculus boolean-algebra
322
questions
0
votes
2
answers
2k
views
Proving equivalency using boolean algebra laws of logic
I have a question on my exam papers relating to proving equivalences using the laws of logic, but I'm not sure how to work it out as I don't have the solution paper.
Can someone explain to me the ...
- 121
1
vote
3
answers
159
views
Propositional Logic : Why is ((p $\Rightarrow$ r) $\land$ (q $\Rightarrow$ r)) $\equiv$ ((p $\lor$ q) $\Rightarrow$ r)
I was working my way through some Propositional Logic and had the following doubt :
Why is this true :
((p $\Rightarrow$ r) $\land$ (q $\Rightarrow$ r)) $\equiv$ ((p $\lor$ q) $\Rightarrow$ r)
...
- 1,503
2
votes
2
answers
2k
views
DNF Form of XOR Operator with N Arguments
I’m working on this problem:
Explain how to express $p$ using the boolean connectives AND, OR, and NOT so that the resulting expression has length polynomial in $n$.
$$p(x_1\cdots x_n) = x_1 \oplus ...
- 21
2
votes
3
answers
76
views
How to show that if $\neg b = a \land d$ then $a \land \neg b = \neg b$ and $b \land \neg a = \neg a$
I'm new to boolean algebra and am having trouble proving the following simple theorem. Many thanks for any help.
If $\neg b = a \land d$ then $a \land \neg b = \neg b$ and $b \land \neg a = \neg a$.
...
- 313
1
vote
1
answer
2k
views
Is infinite boolean algebra atomless?
I got two questions:
1) Does there exist an infinite Boolean algebra which contains an atom?
I answered yes.
2) Does there exist an infinite Boolean algebra B such that for every b contained in B ...
- 141
4
votes
1
answer
2k
views
Finding the atoms and elements of a Lindenbaum–Tarski algebra
Let B be the Lindenbaum–Tarski algebra with three variables $p,q,r$
(1) Find all the atoms of $B$.
(2) How many elements of does $B$ have?
So I think I know what an atom is, but I'm still not sure ...
- 575
7
votes
5
answers
6k
views
Difficulty understanding why $ P \implies Q$ is equivalent to P only if Q.
I have difficulties understanding why $ P \implies Q$ is equivalent to P only if Q. I do understand that in the statement "P only if Q", it means if $ \lnot Q \implies \lnot P$".
Regarding this ...
- 645
2
votes
2
answers
1k
views
Simplification of boolean expression with xor
I need to simplify the following boolean expression
¬(A xor B) xor (B + ¬C)
I know A xor B = ¬AB + A¬B
Then the expression will become
¬(¬AB + A¬B) xor (B + ¬C)
However, I stuck on it and I don't know ...
- 341
2
votes
2
answers
2k
views
How would I go from DNF to a simplified formula with less symbols?
Here's a DNF:
$$(\neg A_1 \land \neg A_2 \land \neg A_3 ) \lor (A_1 \land \neg A_2 \land \neg A_3 ) \lor (\neg A_1 \land \neg A_2 \land A_3 ) \lor (\neg A_1 \land A_2 \land \neg A_3 )$$
And the ...
- 37
2
votes
4
answers
12k
views
Show that (P→Q) ∧ (Q→R) is equivalent to (P→R) ∧ [(P↔Q) ∨ (R↔Q)]
I literally have no idea how to start this proof.
I get to (P→Q) ∧ (Q→R) = (¬P ∨ Q) ∧ (¬Q ∨ R) and then I get stuck.
- 35
3
votes
1
answer
78
views
Going from (p ∧ ~q) ∨ (~p ∧ q) to (p ∨ q) ∧ (~p ∨~q)
I am confused on how to go from (p ∧ ~q) ∨ (~p ∧ q) to (p ∨ q) ∧ (~p ∨ ~q). I know they are equal because I plugged them into a truth table and all of the rows have the same values. What would be some ...
1
vote
1
answer
256
views
AND using XOR and OR?
Is there a way to make an AND using only XOR and OR. I know that a XOR b = ab'+ba' but I have no idea how to proceed.
- 626
2
votes
3
answers
531
views
Construct XNOR with only OR gates
Is it possible to construct the XNOR gate which is given as, a XNOR b = (a AND b) OR (~a AND ~b), by using only OR gates. So from the definition, the question boils down to: can you construct the AND ...
- 21
3
votes
1
answer
117
views
Prove if Tautology, Contradicton, or Neither. Is my proof ok?
Determine whether $((p \Rightarrow q) \Rightarrow r) \Leftrightarrow (p \Rightarrow (q \Rightarrow r))$ is a tautology, a contradiction, or neither.
If $p,q,r
= (0,0,0)$
then $((p \Rightarrow q)\...
- 75
1
vote
1
answer
1k
views
Alternative to xor(A,B,C)
How can we make a comprehensive statement, which will correspond to the truth table of xor (A, B, C) by combining logical operators AND (&), OR (|), XOR (xor) and NOT (!)? In other words, the ...
- 11