Questions tagged [propositional-logic]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
113 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
39 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
83 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
292 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
374 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
34 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
81 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
239 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
185 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
340 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 ...
2
votes
1answer
107 views

What is the set of all minimal 3CNF formulas?

Definition: A minimal 3CNF formula is an unsatisfiable 3CNF formula with minimum clauses connected by conjunctions, where each clause is disjunction of 3 literals, that is if any of it's clauses is ...
3
votes
2answers
212 views

Model disjunction in a $\{0,1\}$ integer linear program

How can I model logical OR as an integer linear program? $$(y_3 + y_4 + y_5 + y_6 = 2) \lor (y_2 = 1)$$ where $y_i \in \{0, 1\}$, $1$ = True and $0$ = False.
1
vote
0answers
62 views

Refutation of pigeonhole using resolution

I am trying to find a way to refute the pigeonhole formula using resolution. Lets assume that $x_{ij}$ is true if $i^{th}$ pigeon is in $j^{th}$ hole. Thus, with $n$ holes and $n+1$ pigeons, the ...
3
votes
1answer
256 views

“Implied atomic propositions” in propositional boolean formula

Suppose we have a propositional boolean formula F and let M be the set of all models of that formula. I am wondering if there is an efficient way to find all atomic propositions that are implied by ...
1
vote
1answer
44 views

Logic, “and” operator between a set of formulas and a formula

Consider a set $S$ of formulas $\beta_i$ and a formula $\alpha$, if we have a condition such as $S \land \alpha$ is inconsistent what we have to calculate to check the inconsistency of $S \land \alpha$...
0
votes
1answer
270 views

Why is learning DNF harder than learning CNF?

In the PAC-learning setting, it is easy to learn a CNF formula when we know each clause has at most $c$ variables. We go through each positive sample, and eliminate every clause that contradicts the ...
2
votes
1answer
122 views

First Order Logic : Predicates

I have a small problem with the first order logic, in particular, predicate logic Let us take this sentence as an example: ...
1
vote
0answers
240 views

Propositional logic in an SMA* algorithm

I'm trying to implement an SMA* graph search algorithm that I found in a paper here(Rong Zhou, Eric A. Hansen: Memory-Bounded A* Graph Search. FLAIRS-02 Proceedings 203-209) and I would like to ...
2
votes
2answers
350 views

How is implication same as entailment

In propositional logic (Artificial intelligence to be specific) $\alpha$ entails $\beta$ iff $\alpha\Rightarrow\beta$ is a statement. However if I write the truth table for implies ($\Rightarrow$) if $...
0
votes
1answer
285 views

What is the simplification of AB + BC + (~B)C?

AB + C is not the answer. The correct answer is AB + BC. HOW?
2
votes
1answer
54 views

In the Resolution equivalence ($\neg A \implies B, B \implies C \models \neg A \implies C$) must $A$ be negated?

The sheet of equivalences given to us in class provides the the equivalences \begin{array}{|c|c|c|} \hline \text{Resolution} & A \vee B, \neg B \vee C \models A \vee C & \neg A \implies B, B ...
1
vote
0answers
33 views

What does the structure ($S_t^x P$) in this Existantial Instantiation imply, Skolemization?

The sheet of equivalences given to us in class provides the two equivalences \begin{array}{|c|c|c|} \hline \text{Universal Instantiation} & \forall x ~ P(x) \implies {S_t}^x P & \exists y ~ \...
0
votes
1answer
140 views

Breaking down CNF clauses

I have an assignment where i have to encode certain problem to conjunctive normal form so i can solve it by using SAT solver. I have been able to encode my problem correctly but the solver is quite ...
-2
votes
1answer
152 views

Use of hypothesis to prove a tautology

Given $$ (¬(P ∧¬Q)⇒S)∧¬P ∧(R⇒¬S) ⇒ ¬R $$ prove that this is a tautology. One way is to use a hypothesis taken from the proposition itself. As an example: If we want to prove this rule: $P ⇒ (P ∧ Q ≡...
1
vote
2answers
63 views

What these simple rules of logical implications mean

Their are many rules of logics, predicate calculus, inferences and syllogisms which haunt me always. It feels better when I find some sensible name to particular rule which also gives me intuition ...
1
vote
1answer
83 views

Propositional logic and connectives(translating to english) [closed]

I want to know some stuff about translating compound statements to english: For the propositions below: p: You have the flu. q: You miss the final examination. r: You pass the course. I want to ...
3
votes
2answers
255 views

Does mutual exclusion hold in this case?

I entered into a discussion with a friend on the following question, which asks if mutual exclusion holds: Consider two processes: $s_1$ and $s_2$ are two variables, set equal initially. P1: ...
3
votes
1answer
96 views

Contingent sentences can always be true

I have a question about contingent sentences. To my knowledge, contingent sentences are sentences that are neither tautologies nor contradictions. In a textbook I read that a sentence might always be ...
22
votes
7answers
8k views

Why is A implies B true if A is false and B is false?

It seems to me that the 'implies' in English language does not mean the same thing as the logical operator 'implies', in a similar way how 'OR' word in most cases means 'Exclusive OR' in our everyday ...
1
vote
1answer
83 views

How to reduce C′A′B + CAB′ to C′B + CB′?

I faced this Boolean expression: $C'(A'B+A)+C(A'+AB')$ It was solved as follows: $C'(A'B+A)+C(A'+AB')$ $=C'(A+B)+C(A'+B') $ ...by applying absorption laws $(I)$ $=C'A+C'B+CA'+CB'$ $=(C\oplus ...
-2
votes
1answer
250 views

Show that the following tautology is a theorem of natural deduction

I'm struggling to apply the theorems of natural deduction to these two examples. $$((p \to q) \land (p \to \neg q)) \to \neg p$$ $$((p \to q) \land (p \to r)) \to (p \to (q \land r))$$ Can anyone ...
3
votes
1answer
371 views

Deciding which logical proposition is stronger

I am studying propositional logic and I am trying to solve some exercise related to the following definition: Given two logical propositions $\alpha$ and $\beta$, we say that $\alpha$ is stronger ...
0
votes
1answer
68 views

Is there any precedence for symbols for constructing parse trees? [duplicate]

I am wondering if some symbols such as the ones in propositional logic have precedence over others in drawing parse trees. For example, the sentence: p ∧ q → r, ...
1
vote
1answer
268 views

What are the differences between parse and decision trees?

I have created a parse tree for the formula: a∧¬(b∨c)∨¬d∧(¬b) successfully. I am now asked to create a decision tree for the same formula. What are the main differences between a parse tree and a ...
-2
votes
1answer
144 views

All output functions of a truth table

http://www.cim.mcgill.ca/~langer/273/3-notes.pdf I can name one more: XNOR. But besides these, what other output functions are there?
5
votes
2answers
1k views

How to read out a double negation in propositional logic

How would one verbally say ~~R where R = my program is correct? The tildes are negation symbols. I'm not sure if it just cancels out and comes out as 'my program is correct' or if it's something else. ...
2
votes
1answer
170 views

Equivalent formulae with different CNF

I was not able to find or come up with two formulae which are equivalent but have different CNF. All my ideas reduce to the same formula after applying transformations. The requirements are the ...
2
votes
1answer
31 views

Derivation of implicational propositional axioms

Is there a way to subtract and add properties of axioms to generate new axioms? For example: {L} = {P S K} // natural deduction {P S K} = {P H K I} // natural deduction {S K} = {?} // constructive ...
2
votes
1answer
373 views

What are the differences between propositional logic and temporal logic?

I am currently studying temporal logic and find it much similar to propositional logic. However, temporal logic seems to be slightly more specific because it encapsulates more precise meaning symbols, ...
0
votes
1answer
73 views

a program discovering himself how to solve propositional calculus

it is well-known that propositional logic problems such as $$ (p\leftrightarrow q) \lor r \quad\overset{?}{\vdash}\quad (((p\lor q)\to(p\land q)) \land \lnot r)\lor r$$ can be simply solved by ...
3
votes
1answer
112 views

complexity of modal logic axioms

I am writing a paper in which I want to include complexity results for different modal logics and possibly add a reference to a specific paper. At the moment I have the following: K- no restrictions ...
3
votes
1answer
346 views

Iota combinator and implicational propositional calculus

There is are two esoteric languages with minimally functionally complete operators, iota and jot, that are closely related to SK combinators. I'm attempting to understand the relationship between ...
-1
votes
2answers
227 views

Which formula corresponds to this K-Map?

I have a K-Map and I need to figure out which expression isn't equivalent to the provided K-Map. $f(w,x,y,z) = \sum(3,7,9,11,13,15) + \Phi(4,5,6)$ We know that both options (a) and (b) are ...
0
votes
1answer
208 views

Relations between statements involving universal quantifier, conditional and biconditional

If we consider two predicates: $b(x)$: x is a boy $c(x)$: x is clever Then, there are four statements involving $∀, b(x), c(x), →$ and $↔$ . These are below along with my interpretation of their ...
-2
votes
1answer
48 views

Transform $A\land B \Leftrightarrow B\lor A$ into conjunctive normal form [closed]

How do I transform the following formula into conjunctive normal form? $$ A \land B \Leftrightarrow B \lor A $$
5
votes
1answer
182 views

How to find a minimum set of axioms within a set of propositions?

I have a set of propositions, for example $\{a_1,a_2,\dots,a_n\}$. Some propositions depend on others (for example, $a_1,a_2\Rightarrow a_3$, means if $a_1,a_2$ are true, then $a_3$ is true). I want ...
4
votes
2answers
2k views

Find hamilton cycle in a directed graph reduced to sat problem

I need to find a Hamiltonian cycle in a directed graph using propositional logic, and to solve it by sat solver. So after I couldn't find a working solution, I found a paper that describes how to ...
0
votes
1answer
708 views

How to decide if a propositional formula is a well formed?

So, I have the following propositional formula: (((P → Q) ∨ S) ↔ T) How do I decide if it's well formed?
1
vote
1answer
78 views

Non-deterministic algorithms and Tautologies

I am studying the lecture The Complexity of Propositional Proofs. ​Here there is a definition together with a discussion (page 3). I don't understand that discussion. Let $F$ denote the set of ...
1
vote
1answer
300 views

Size of Propositional Formula

I am study this lecture The Complexity of Propositional Proofs. Here there is a term size of propositional formula (page 2), Every tautology $\tau$ on $n$ variables has an $F$-proof in which thera ...