All Questions
Tagged with propositional-calculus boolean-algebra
322
questions
2
votes
2
answers
49
views
Propositional equivalence. Duality problem.
I recently have started practicing problems on Discrete Mathematics by Keneth H.Rosen. There seems to be an interesting problem on Propositional Equivalence which states that when is $s^{*} = s$. ...
1
vote
1
answer
368
views
Factoring a XOR Expression in an Equation
I have an equation like this: $(i_1 \cdot x) \oplus (i_2 \cdot x) = r$ where $i_1, i_2,$ and $r$ are known values and $\oplus$ is xor.
What I need is that same equation but expressed as $i_3 \cdot x = ...
- 13
0
votes
1
answer
280
views
How to get CNF of propositional formula form DNF of its complement?
Explain how to read off a CNF for propositional formula directly from a DNF from its complement.
I've managed to explain it in words, but can't write a rigorous proof of that. How to show this in ...
user752336
-1
votes
1
answer
86
views
Logic Identity for $\mathcal{(A'B)}$+$\mathcal{(AB')}$
I need to simplify a long boolean expression and I am stuck with this expression
$$\mathcal{(A'B)}\text{+}\mathcal{(AB')}$$
Can I simplify that to $\mathcal{(AB)'}\large\text{ ?} $
And if so, what ...
0
votes
1
answer
668
views
Showing all boolean functions can be expressed by only conjunctions or negations
Let $f:$ {T,F}$^n \rightarrow$ {T,F}, i.e a function of n boolean variables.
Show that each $f$ can be expressed as a formula of only conjunctions and negations, and give an upper bound for the number ...
- 33
2
votes
2
answers
315
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
0
votes
0
answers
103
views
Boolean Algebra Simplification Unknown Step Introduce Variables
I've been trying to interpret a logical proposition for several days. I need to simplify, I can't do it with the laws that I know, but using online tools I can find the result, but in the step by step ...
- 1
3
votes
1
answer
90
views
proof that any boolean function can be written in canonical form
It's bugging me for a while but although I can vaguely see that when writing canonical forms we kind "build them" in a way specificly to make it be true but I can't grasp exactly why it is ...
- 35
3
votes
4
answers
832
views
How is material implication the same as subset?
I've been told and read a number of times that implies, $\implies$, is the same as subset $\subseteq$. For example, in the wikipedia page on iff it states that "P only if Q", "if P then ...
- 1,324
1
vote
0
answers
92
views
How do I prove this logical equivalence?
$\phi$ is a well formed formula.
f($\phi$) is given by replacing ∧ with ∨ (and vice versa) and 1 with 0 (and vice versa) in $\phi$.
g(f($\phi$)) is given by replacing all literals in f($\phi$) (...
- 111
0
votes
1
answer
65
views
How to formally write "Let $X$ take on the value of TRUTH"?
I have to argue that a given logical expression is satisfiable and not universally applicable. This is quite easy because all I have to do is find for which values is the expression true and false. ...
- 1,928
1
vote
1
answer
71
views
Show that ($\lnot$q $\implies$ p) $\implies$ (p $\implies$ $\lnot$q) $\equiv$ ($\lnot$p $\lor$ $\lnot$q) using the conditional-disjunction equivalence
Conditional-disjunction equivalence:
(p $\implies$ q) $\equiv$ ($\lnot$p $\lor$ q)
To show:
($\lnot$q $\implies$ p) $\implies$ (p $\implies$ $\lnot$q) $\equiv$ ($\lnot$p $\lor$ $\lnot$q)
Attempt:
...
- 141
0
votes
1
answer
66
views
DNF to CNF of a simple expression
I have a formula like this:
$$\bigvee_{\substack{i \in [1,...,m] \\ j \in [1,...,m]}} x_{i} \wedge x_{j}$$
What is the equivalent formula in CNF (conjunctive normal form)?
- 81
1
vote
1
answer
76
views
CNF formula for manipulating words
I am trying to create CNF formula for manipulation of a word. word is a sequence of letters from a $\Sigma$ alphabet. A word is encoded by variables like $x_{i,a}$ which means that the letter $a$ is ...
- 81
0
votes
1
answer
55
views
CNF for modilisation of a word
Imagine that we are interested in problem of words. A word is a sequence of letters from a $\Sigma$ alphabet. For encoding a word in SAT we are using variable like $x_{i,a}$ which means that in ...
- 81