All Questions
Tagged with propositional-calculus boolean-algebra
322
questions
2
votes
3
answers
85
views
Logical Equivalence for $p \lor q$
I have to prove that
$$p \vee q \equiv (p\wedge q) \vee (\neg p\wedge q) \vee (p\wedge \neg q)$$
Based on the truth table, they are equivalent, but I couldn't figure out how to use logic statements to ...
- 139
2
votes
1
answer
610
views
Boolean algebra - Converting DNF form to CNF
I've tried at least a dozen ways to convert this DNF to CNF, yet I always end up with something unusable. Here is the DNF:
$$y= (A \wedge B \wedge \neg C \wedge D) \vee (A \wedge B \wedge C \wedge \...
- 21
2
votes
4
answers
158
views
Proof that $B \land ( B \lor C) = B$?
In my logic design exam today I was given this question:
Show that:
$$ B \land ( B \lor C) = B $$
It's asking for a proof for this expression. Could someone please explain how such expression ...
user54251
2
votes
1
answer
92
views
Is the structure of propositional logic axiomatizable by the axioms of Boolean algebra?
I think that the following question has a positive answer. Yet, I haven't managed to find it.
Consider the structure $\{0,1\}$ with operations $\lor,\land,\lnot$ defined in a usual way.
Is it true ...
- 1,773
2
votes
2
answers
319
views
What is "X happens whenever Y happens"?
This page says "$X$ happens whenever $Y$ happens" translates to $Y \implies X$. But I feel $Y\implies X$ allows $X$ to be $True$ when $Y$ is $False$, which does not seem to be correct for &...
- 187
2
votes
3
answers
130
views
Show functional completeness of $\{\nleftarrow, \sim\}$ (inhibition, negation) via structural induction
I came across an exercise which asks to determine via structural induction whether the connective set {$\nleftarrow$, $\sim$} is a functionally complete set, knowing that the set {$\wedge, \vee, \sim$}...
- 31
2
votes
2
answers
8k
views
Absorption Law proof
I know this was answered before but I'm having one particular problem on the proof that I'm not getting.
My Understanding of the distribution law on the absorption law is making me nuts, by the ...
- 23
2
votes
1
answer
228
views
If every truth assignment satisfies some wff, some finite disjunction is a tautology
Let $X_1,X_2,X_3,...$ be well formed formulas. If for every truth assignment $v$ there exists $n$ with $X_n$ satisfied by $v$, show there exists $n$ with $X_1\lor...\lor X_n$ a tautology.
We can ...
user665538
2
votes
1
answer
212
views
What is the "official" name for these boolean algebra rules?
In boolean algebra, we have the following simplification rules: $$P + (\ldots P \ldots) = P + (\ldots 0 \ldots)$$ and $$P \cdot (\ldots P \ldots) = P \cdot (\ldots 1 \ldots)$$ (Here $\;\ldots P \...
2
votes
1
answer
421
views
Rewriting logical proposition which is in compact (implicit) notation.
I have:
$$\bigwedge_{i=1}^{9} \bigwedge_{n=1}^{9} \bigvee_{j=1}^{9}~p(i,j,n)$$
I want to rewrite it so that to make the bottom part look like i=1 j=1 n=1 and also ...
- 368
2
votes
2
answers
1k
views
Is it ok this CNF of a Boolean function?
I have to find out the CNF of $$\begin{matrix} f(x,y,z)&=&(x\wedge y)\vee(x\wedge z),\end{matrix}$$ where $f$ is a Boolean function.
$$\begin{matrix}&f(x,y,z)&=&(x\wedge y)\vee(x\...
- 2,269
2
votes
2
answers
67
views
Simplification of a Boolean function
Let
$$f(x_1, x_2, x_3) := \sum m(2, 3, 4, 5, 6, 7)$$
With the normal SOP expression for this function, it must be, with the use of minterm:
$$f = m_2 + m_3 + m_4 + m _6 + m_7 = x_1'x_2x_3'+x_1'...
2
votes
1
answer
68
views
How would I be able to reduce this boolean expression? $(b + d)(a' + b' + c)$
So, I have this boolean expression and I have to simplify it, here is what I am doing:
$(b + d) * (a' + b' + c)$
*Opening the expression by multiplication
$= a'b + bb' + bc + a'd + b'd + cd$
$= a'...
- 239
2
votes
1
answer
840
views
Universal 2-bit gates
I'd like to show that there is no set of 2 bit reversible gates which is universal. I'm not sure as to where & how do I start here? I tried to assume by contradiction that such a set exists, thus ...
- 935
2
votes
4
answers
188
views
How to prove this tautology using equivalences?
I am trying to prove that the following is a tautology:
$(A \implies (B \implies C)) \implies ((A \implies (C \implies D)) \implies (A \implies (B \implies D)))$
To make progress, I thought I'd ...
- 197