All Questions
Tagged with propositional-calculus boolean-algebra
37
questions with no upvoted or accepted answers
3
votes
0
answers
103
views
Do the integers 1 and 0 mean different things in Boole's original logic and modern Boolean algebra?
I understand that the modern notion of Boolean algebra was adapted by Peirce, Schroder and others from Boole's logic of classes. Boole spoke of 1 and 0 as representing the Universe of Discourse and ...
- 79
2
votes
0
answers
37
views
When are two propositional formulas dependent?
The following question has arisen when considering dependencies induced by probabilistic logic programs:
Let $A_1, \dots, A_n$ be proposition symbols, and let $\Omega_n$ be the set of all truth value ...
- 31
2
votes
0
answers
60
views
Are ultrafilters precisely the designated sets in semantics(es) for classical logic?
I'm messing around with ultrafilters to try to understand them better. It seems as if ultrafilters work well as sets of designated truth values in matrix semanticses for classical logic.
This also ...
- 11.9k
2
votes
0
answers
254
views
How can I find the CNF of ($A$ and $B$ or $C$) and ($B$ or not $C$) using a Karnaugh map?
$$(A\land B \lor C) \land (B \lor \lnot C)$$
I know how to create the truth table and Karnaugh map of a logic expression. But I couldn't find exactly how to calculate the simplified CNF of it using ...
2
votes
0
answers
68
views
why does a closed circuit represent a false proposition? (Claude Shannon thesis)
In reading through Claude Shannon's paper: A Symbolic Analysis of Relay and Switching Circuits.
As a software engineer, I got confused by Shannon's choice to have 0 as representing a closed circuit, ...
- 277
2
votes
0
answers
150
views
How many distinct subsets of binary boolean operators are closed under composition?
Question:
There are $2^4=16$ distinct binary boolean operators. Two operators are regarded the same if one can be obtained from the other by exchanging the operands (input). It is easy to see only $...
- 4,243
2
votes
0
answers
142
views
Boolean algebras as models of (quantifier-free) monadic predicate logic
Suppose we have a Boolean algebra over $n$ bits, meaning when viewed as a vector space over $F_2$, the dimension is $n$.
Then we can define $n$ unary predicates $P_n$ which return the value of the $n$...
- 8,000
1
vote
0
answers
73
views
How to show $\{0, \vee, \leftrightarrow \}$ is functionally complete/ incomplete?
I'd like to provide an attempt, but all I can think off is trying to construct one of the following complete set of boolean functions and have been unsucessful in that. I can only get an additional ...
- 871
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
1
vote
1
answer
259
views
Rewriting a boolean expression using different literals
I'd like to implement an algorithm to rewrite a boolean expression as a sum of products of different boolean expressions (expressed as new literals).
Example
Let's say that I have some literals $A_0,...
- 111
1
vote
0
answers
68
views
can you help me find the dnf of this expression ? i got messy
I want to find the DNF of the following expression but it got all messy.
I also tried it in wolfram alpha, and of course it showed i really need the steps you need to make to get there $\dots$
This ...
- 11
1
vote
0
answers
1k
views
A reduction of 3-CNF down to 2-CNF for boolean satisfiability
Could you please review the following candidate solution for the boolean satisfiability problem?
It is known that 2-CNF has a polynomial solution.
Now consider we have a 3-CNF (AFAIK, it's proven ...
- 153
1
vote
0
answers
284
views
How to prove something is not a logical consequence of 2 propositions.
I have a question where I have to show that the third statement is not a logical consequence of the 1st two using a truth table. I've seen how you'd do if there are only two (How to prove logical ...
1
vote
0
answers
51
views
Is this a Boolean algebra? (proof)
Let $B=\{0,1\}$ and the binary operations $\oplus,\cdot$
We define a bijection $\varphi$ s.t.:
$$
\varphi:B \longrightarrow L=\{\mathbf{False},\mathbf{True}\},
$$
$$
\varphi(x):=
\begin{cases}
\...
- 2,031
1
vote
2
answers
194
views
SOP expression simplify
I wanted to know how to simply this SOP expression using Boolean Algebra :
F= A'BC'+A'BC+ABC
I got this answer using K - Map: (A'B+BC), but I want to know how do get it using Boolean Algebra Rules.
...
1
vote
0
answers
140
views
Propositional formula proof, general version.
I'm really stuck at proving general versions for any propositional formula for example:
I) Use truth table to prove this De Morgan's law
$$ \lnot (P \land Q) \equiv \lnot P \lor \lnot Q $$
Which ...
- 159
1
vote
0
answers
61
views
Model checking in epistemic logic
I am trying to program a model checker for dynamic epistemic logic, but I am not quite sure how to do it.
As far as I understand, model checking means to take a propositional formula and go through ...
- 819
1
vote
0
answers
112
views
how to determine if formula satisfies without creating a truth table
$(p \wedge q \wedge r) \wedge (\neg p \vee r)$
So far, what I have got is that $(p \wedge q \wedge r)$ satisfies because if $p$, $q$ and $r = 1$ then $(p \wedge q \wedge r)$ also $= 1$. For $(\neg p \...
- 11
1
vote
0
answers
254
views
Monotonic operators in classical logic
Which means monotony for a logical operator, and affinity, in propositional calculus affinity..., here on wiki do not quite understand!!
- 379
1
vote
0
answers
784
views
Dual formula in propositional logic
There's something I don't understand in my course on propositional logic.
In the case of x being a variable, the definition of its dual is x* = x. Right.
However, further in the course, there's a ...
- 11
1
vote
0
answers
737
views
Inverse function in multi-valued logic through the Webb function
Let Webb function in multi-valued logic as $Webb(x, y) = W(x, y) = Inc(Max(x, y))$. There is a theorem about any function in any multi-valued logic can be represented through the Webb function.
Then ...
- 1,211
0
votes
0
answers
34
views
A generalized algorithm to convert a formula in algebraic normal form to an equivalent formula that minimizes the number of bitwise operations
In this question, “bitwise operation” means any operation from the set {XOR, AND, OR}. The NOT operation is not included because ...
- 922
0
votes
0
answers
45
views
Can any finite set of binary sequences be expressed as CNF/DNF
I am new to logic and cannot figure out if there are instances when a given set of binary sequences of equal length is not possible to express as a conjunctive or disjunctive normal form. If such sets ...
- 397
0
votes
0
answers
84
views
Prove $\vdash(A\supset B)\supset C\equiv C\overline{\vee }[A\wedge \neg(B\vee C)]$ using your favorite method
I've been playing with Boolean logic vs ordinary laws of logic like DeMorgan's etc., and I've come up with the following theorem in about 4 lines: $$[(A\supset B)\supset C]\equiv \left\{C\overline{\...
- 1,545
0
votes
0
answers
138
views
Provide a few examples of Boolean algebra where carrier is a finite set of finite sequences (ordered set)
I study Boolean Algebra and it is clear when: (carrier is a power set, union, intersection), (set of all divisors of n, lcm, gcd), (the set of propositional functions of n given variables, conjunction,...
- 435
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
0
votes
3
answers
73
views
Why is $ (a \lor b \lor c) \oplus ( a \lor b)$ equivalent to $\lnot a \land \lnot b \land c$?
I'm having a hard time understanding why $(a \lor b \lor c) \oplus (a \lor b)$ (where $\oplus$ stands for XOR) is equivalent to $\lnot a \land \lnot b \land c$ in propositional logic. Any help would ...
- 9
0
votes
0
answers
38
views
How to solve this boolean logic question?
Formalise the following argument in Boolean logic, and decide whether it is correct or not.
Explain your answer.
If the burglar is from France, then he is tall. If he is tall, then he came through ...
- 115
0
votes
0
answers
36
views
Are the statements equal?
Is this true?
$$ \bigwedge_{i=1}^{9} \bigwedge_{n=1}^{9} \bigvee_{j=1}^{9}~p_{i,j,n} \Longleftrightarrow \bigwedge_{i=1}^{9} \bigwedge_{n=1}^{9} \bigvee_{j=1}^{9}~p_{(i,j,n)} \Longleftrightarrow \...
- 368
0
votes
0
answers
70
views
What kind of algebraic structure is the one with NAND?
In her book Model Theory, María Manzano mentions the following kinds algebraic structures:
Group
Rings and fields
Order
Well-order
Peano structures
Boolean algebras
Bolean rings
Nevertheless, it's ...
- 451