Questions tagged [propositional-logic]
The propositional-logic tag has no usage guidance.
3
votes
1answer
26 views
Matrix Representation for logical gates?
I have been trying to find if there are other matrix type representations logical circuits, in the example below, $$\begin{bmatrix} 1 & 0\\ 1 & 1\\ \end{bmatrix} \equiv \, \, \Rightarrow$$ ...
1
vote
0answers
22 views
Why Modus ponens works with Horn clauses and Generalized Modus ponens requires definite clauses?
I am reading the Artificial Intelligence: A Modern Approach book and in the chapters about logic i noticed that in propositional logic the Modus ponens inference rule (used by the forward and backward ...
1
vote
1answer
29 views
What is the computational complexity of intuitionistic propositional logic?
Consider the decision problem: given formulas of propositional logic $\phi_1, \ldots, \phi_n, \psi$, determine whether $\phi_1, \ldots, \phi_n \vdash \psi$ intuitionistically. This problem is well-...
0
votes
1answer
36 views
Finding CNF of $(p \rightarrow q) \rightarrow p$ and $\lnot (q \wedge (\lnot p \rightarrow q)) $
I'm trying to find the CNF of the $(p \rightarrow q) \rightarrow p$ and $\lnot (q \wedge (\lnot p \rightarrow q))$, and afterwards proving it's validity. As i'm new to CNF i wanted to ensure i've ...
1
vote
0answers
17 views
Is there a formula that is not logical equivalent to any Horn clause?
There are of course formulas that can't be transformed into a Horn clause but is it possible to construct an equivalent Horn clause that is true under the same interpretation?
1
vote
0answers
26 views
How to minimize large DNF formula into deeper but smaller formula?
I want to minimize DNF formula which has ~200k products combined into a sum.
The depth of that formula is 2 - first level is the OR, and second level is AND for all conjunctions.
I have tried using ...
-1
votes
1answer
18 views
C logical consequence of S iff S union {-C} UNSAT
I'm trying to do the following demonstration:
(C and S are CNF)
C is a logical consequence of S iff. S u {-C} UNSAT
And I did the following:
C is a logical consequence of S iff. S u {-C} UNSAT iff.
...
2
votes
1answer
39 views
Does it hold that $F \equiv \sigma(F)$ for a CNF formula $F$ and a permutation $\sigma$ s.t. $F \vDash \sigma(F)$?
Suppose we have a CNF formula $F$ and a permutation $\sigma$ of its literals such that for any literal $x, \sigma(\neg x)=\neg \sigma(x)$ and $F \vDash \sigma(F)$.
Does it hold that $F \equiv \sigma(...
4
votes
1answer
35 views
Knight and knaves
I have these in my lecture notes, its about the rules where knights always tell the truth and knaves always lie:
If A says “The statement ‘there is gold on the island’ and the statement ‘I am a ...
1
vote
1answer
31 views
Preserving a propositional formula
I know I must be getting stuck on notation. However, I'm having trouble following the logic in Example 1.2 in https://arxiv.org/pdf/cs/0611018.pdf. They define what preserving a propositional ...
0
votes
0answers
15 views
What production rules produce propositional logic tautologies?
Production rules correspond to Turing machines:
[U]nrestricted grammar[s]...can generate arbitrary recursively enumerable languages.
There is a Turing machine that can recognize tautologies in ...
1
vote
1answer
57 views
How to define the Atomic Propositions in Model Checking
The atomic propositions in Symbolic Model Checking form the state in the state-transition graph (the model $\mathcal{M}$ in Model Checking). The other part of Model Checking is the specification, ...
2
votes
1answer
49 views
Are there any techniques for checking whether a clause is subsumed by another clause when adding it to a cnf formula?
When doing variable elimination on a formula in cnf form, there is created a lot of new clauses. Is there any efficient way to check if these are subsumed by other, already existing clauses?
1
vote
1answer
30 views
Resolution Algorithm - No new clauses
The standard resolution algorithm returns false if no new clauses are added.
I know that if $KB \land \neg a \implies []$, it returns true by proof by contradiction, but how can I understand the ...
3
votes
1answer
68 views
What is the connection between combinatorial circuits and finite state automata?
The diagram on the Wikipedia page of FSA shows the hierarchy of the computational devices, in that diagram it is denoted that the finite state machines are superior to the combinatorial circuits.
...
0
votes
2answers
68 views
Can any memory-less computer operation be represented in propositional logic?
Take any operation that is done by any type of computer (e.g. a cpu on a modern laptop), which doesn't use any type of temporary memory storage.
I.e. this computer operation computes a function $f(x)=...
0
votes
0answers
31 views
Give context-free grammars that generate formulas in: [duplicate]
Give context-free grammars that generate formulas in propositional calculus, taking into account:
variables represented by single lowercase letter
Operations are conjunction (∧), disjunction (∨), ...
0
votes
1answer
22 views
Convert (x + y = z) to propositional logic formula for 8-bit numbers
(Note: this was asked in the cstheory stackexchange, but I was told this is a more appropriate place for it.)
I have three 8-bit 2's-complement numbers (X, Y, and Z). I want to find a propositional ...
1
vote
0answers
45 views
What is the definition of the property of Canonicity for a logic?
I'm trying to understand "A Systematic Approach to Canonicity in the Classical
Sequent Calculus" by Kaustuv Chaudhuri, Stefan Hetzl, Dale Miller. The article discusses a property called "canonicity" ...
0
votes
1answer
56 views
Inference rules for deriving invariants in Hoare logic
The following algorithm is supposed to compare two strings $S_1$ and $S_2$ ("/\" for empty string):
...
0
votes
0answers
41 views
How to construct an NFA Ai for the given Regular property P1 and P2?
Let AP = {a; b; c}.
Consider the following regular safety properties:
(a) P1: If a becomes valid, afterwards b stays valid ad infinitum or until c holds.
(b) P2: Between two ...
18
votes
4answers
5k views
Can proof by contradiction work without the law of excluded middle?
I was recently thinking about the validity of proof by contradiction. I’ve read for the past few days things on intuitionistic logic and Godel’s theorems to see if they would provide me answers to my ...
12
votes
5answers
2k views
Why does soundness imply consistency?
I was reading the question Consistency and completeness imply soundness? and the first statement in it says:
I understand that soundness implies consistency.
Which I was quite puzzled about ...
5
votes
1answer
218 views
Implementing mathematical theory of arithmetic in Haskell via Curry-Howard correspondence
I have to ask for forgiveness in advance if the whole question doesn't
make a lot of sense, but unfortunately, I have no better intuition as
of right now and this seems like the best starting point I ...
1
vote
2answers
386 views
how to solve Hoare logic problems
I'm having trouble proving Hoare logic questions as I'm not sure of the process that is taken to prove them. I understand that they're rules such as assignment axiom, pre-condition strengthening, post-...
0
votes
1answer
67 views
Does exist NP language that is Cook Levin deterministic reducible to xor satisfiability in polynomial time?
We say that the language $L$ is Cook Levin deterministic reducible to xor satisfiability in polynomial time if and only if for each word $w\in\Sigma^*:w\in L\iff f(w)\in XORSAT$ where $\Sigma=\{0,1\}$ ...
0
votes
1answer
105 views
Is this possible to solve satisfiability by using Quine McCluskey algorithm to simplify the whole given boolean formula by simplifying subformulas?
In this question
Farewell Stack Exchange suggested to use karnaugh maps to solve the satisfiability problem by simplifying the entire/whole boolean formula by simplifying subformulas until you have ...
0
votes
2answers
506 views
Which of the following expressions is TRUE if and only if NOT all three variables a, b, and c have the same value?
I am trying to solve this problem and I am stuck. I think it is B, but I think I'm wrong. Thanks.
Which of the following expressions is TRUE if and only if NOT all three variables a, b, and c have ...
3
votes
3answers
172 views
Does exist any horn formula that is equisatisfiable to the clause that is disjunction of two literals? Does also exist equivalent?
I just and simply want to know if whether or not exist any horn formula that is equisatisfiable to $(p\lor q)$. I would also be interested to know if there also exists equivalent.
3
votes
1answer
223 views
How to estimate how many assignments satisfy a given DNF formula using Monte Carlo?
Admittedly, homework.
For the purpose of this question: $\phi$ is a DNF formula similar to this one: $(x_1 \wedge \neg x_3 \wedge x_4) \vee (\neg x_1 \wedge x_2)$ Also $C_i$ is a clause in this ...
3
votes
2answers
78 views
Why algorithms calculating non-tirivial zeros can't be used as proofs of Riemann Hypothesis?
Recently I was reading again this propositions as types paper by Philip Wadler:
http://homepages.inf.ed.ac.uk/wadler/papers/propositions-as-types/propositions-as-types.pdf
It gives an impression, ...
0
votes
1answer
73 views
How to adapt DPLL to solve HORNSAT?
This question wask asked in a homework of Computer Theory in Rome, Italy.
How to simplify the DPLL algorithm in order to solve HORNSAT?
My Approach:
I know that an Horn clause is an OR of ...
21
votes
11answers
4k views
Why is $A \lor (A \land \neg B) \equiv A$?
I would like to know if there is a rule to prove this. For example, if I use the distributive law I will get only $(A \lor A) \land (A \lor \neg B)$.
-4
votes
1answer
92 views
Valid, unsatisfied or neither? [closed]
How should I create the truth table to solve each of these questions? Maybe can give me an example?
$Smoke \implies Smoke$
$Smoke \implies Fire$
$(Smoke \implies Fire) \implies (\neg Smoke \implies \...
1
vote
3answers
49 views
Expressing statements on elephants in propositional logic
If I wanted to create a sentence like:
African elephants can carry coconuts; Asian elephants cannot.
How would I do that with propositional logic?
2
votes
4answers
168 views
Is it necessary to learn how to prove Mathematical theorems as a CS Student? [closed]
I've just started my undergraduate course and have tried my hands on MIT's OpenCourseWare on Discrete Math on Logic and Proofs. There was a particular question asking to prove Cantor's Theorem:
...
1
vote
1answer
145 views
Question on Predicates and Quantifiers
I am reading from "Discrete Mathematics and Its applications" by Kenneth H. Rosen, 7th edition. Consider the highlighted part in the following example taken from the same book:
Question Use ...
0
votes
1answer
112 views
cancel out parts of a formula in CNF (conjunctive normal form)
In this image there is a given formula in DNF and CNF. When I check it on Wolfram Alpha I see that it cancel out (E or D) because of (not A or A) which is colored in red. My question is if it is ...
0
votes
1answer
46 views
Understanding kQBF: changing order of quantification?
2QBF is a problem of determining whether formula $\exists X~\forall Y:\varphi(X,Y)$ is valid. $X$ and $Y$ here are sets of variables. Next, 3QBF asks if formula $\exists X~\forall Y~\exists Z:\varphi(...
0
votes
1answer
40 views
Does every 3CNF propositional formula has an equisatisfiable 2CNF propositional formula
Does every 3CNF propositional formula has an equisatisfiable 2CNF propositional formula?
1
vote
1answer
72 views
Does every 3CNF propositional formula has an equivalent 2CNF propositional formula?
Does every 3CNF propositional formula has an equivalent 2CNF propositional formula?
Definitions:
3CNF propositional formula is conjunctive normal form propositional formula, which is just ...
0
votes
0answers
28 views
Resolution with multiple variables
Resolution allows to generate new clauses for an existing set of clauses.
In many cases, the rule is simple:
...
0
votes
0answers
63 views
Convert conjunctive normal form to equivalent boolean formula with only NOR gates
Let $\varphi$ be a boolean formula in 3-CNF form (conjunctive normal form with three literals at most per clause). I want to convert it to an equivalent boolean formula that uses only NOR gates with ...
0
votes
1answer
196 views
Convert conjunctive normal form to equivalent boolean formula with only NAND gates
Let $\varphi$ be a boolean formula in 3-CNF form (conjunctive normal form with three literals at most per clause). I want to convert it to an equivalent boolean formula that uses only NAND gates with ...
1
vote
1answer
273 views
Is this possible to solve boolean satisfiablility by using karnaugh maps to simplify the whole given boolean formula by simplifying subformulas?
Building karnaugh map for the whole given boolean formula always costs Θ(2n) both time and space complexities, where $n$ is the number of boolean variables in the given boolean formula.
It is ...
1
vote
1answer
30 views
What is the largest possible minimal 3CNF formula as function of the number of variables?
I have already defined here what is minimal 3CNF formula.
In the answer to the question, D.W. answered:
What you are thinking is wrong. A minimal, unsatisfiable formula can have more than 8 clauses.
...
2
votes
1answer
59 views
What is the set of all maximal 3CNF formulas?
Definition: A maximal 3CNF formula is satisfiable 3CNF formula, but if you conjuct it with another any new different 3 disjuctive literals clause, then the formula becomes unsatisfiable.
Please don't ...
1
vote
1answer
146 views
What is the complexity of determining whether or not conjunction of positive CNF and negative CNF is satisfiable?
Definitions:
positive CNF is a conjunctive normal form formula, where all literals are positive, i.e. the unary connective ¬ does not exist in the formula.
negative CNF is a conjunctive normal ...
0
votes
1answer
151 views
Proving unsatisfiability of a propositional formula
I have a propositional formula $F$ and an assignment of truth variables $A$. The assignment $A$ assigns a truth value to each variable in $F$ and then it can be evaluated.
I have a function which for ...
1
vote
1answer
245 views
Is this possible to solve 4SAT in polynomial time? [closed]
I know and admit that this is long, but please read it slow and understand everything.
I think that this is one of the most interesting questions asked in computer science ever.
I don't expect for ...
