Questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions would fit very nicely under this tag. Questions about other kind of logics should be tagged with [logic] instead.

learn more… | top users | synonyms (1)

0
votes
0answers
32 views

Optimal assignment for an unsatisfiable formula

Given an unsatisfiable formula $F$ in CNF, are there any methods to find an assignment that can satisfy as many clauses as possible?
1
vote
1answer
54 views

Resolution Algorithms and one Example Problems?

We have a problem in one Resolution question. There is $5$ clauses, and want to prove the $6$th clause is true. which of the following clause is need more than one times to prove $6$th clause? $t$ ...
1
vote
1answer
55 views

CNF Conversion and one $2015$ exam questions?!

if $\text{likes}(x,t)$ means that person $t$ likes food $x$, and $\text{food}(x)$ means $x$ is a food, $\text{CNF}$ of sentence "No food is liked by all person", and $F$ is Skolem function. The ...
3
votes
4answers
88 views

Why does “if and only if” mean the exact same thing as “precisely when”?

The proposition "A precisely when B" states that A has the same truth value as B. The proposition "A if and only if B" states that A is true if B is true and that A is true only if B is true. ...
3
votes
3answers
59 views

Prove that $(p \to q) \to (\neg q \to \neg p)$ is a tautology using the law of logical equivalence

I'm new to discrete maths and I have been trying to solve this: Decide whether $$(p \to q) \to (\neg q \to \neg p)$$ is a tautology or not by using the law of logical equivalence I have ...
0
votes
4answers
75 views

Proving $(H \implies H) \implies G \quad \therefore \quad G$ using natural deduction [closed]

I'm stuck on this extra credit logic problem for my course... Prove $$(H \implies H) \implies G \quad \therefore \quad G$$ using methods of natural deduction. Any help would be ...
4
votes
5answers
390 views

Negation of the definition of limit

A sequence $(x_n) $ of real numbers converges to a real number $ x $ if For all $\epsilon> 0 $ there exists a natural number $ n_0 $ such that for all $ n \ge n _0 $, $|x_n - x| < \epsilon $. ...
0
votes
1answer
32 views

Discrete Mathematics - Quantifiers problem

This is a question from the Discrete Mathematics question from Kenneth Rosen book. I didn't understand the question and thus I am confused how to begin with question. Below is the question from the ...
0
votes
1answer
26 views

Quantifiers Kenneth Rosen Discrete Mathematics

Please help me in regard with this question.I didn't have a clue how to solve this. The way I thought about this question is assuming the truth values of predicates P(x) and Q(x) and then trying ...
1
vote
1answer
63 views

Prove that $ \text{len}(q^*) \le 3\text{len}(q) -2 $

Prove by induction where q is a formula in proposition logic: $$ \text{len}(q^*) \le 3\text{len}(q) -2 $$ Where the star property (*) is defined as follows: $$ \text{atom}^* = \text{atom} $$ $$ (\...
2
votes
1answer
44 views

From an axiom system of propositional logic to an axiom system for a Boolean algebra

A well-known set of axioms for the classical propositional logic is Lukasiewicz's 3rd set: $A\rightarrow(B\rightarrow A)$ $(A\rightarrow (B\rightarrow C)\rightarrow ((A\rightarrow B)\rightarrow (A\...
0
votes
2answers
54 views

Prove that if $ \Gamma $ is inconsistent, then $\Gamma \vdash \beta $ for every formula $\beta$

Considering that $\Gamma$ is inconsistent if $ \Gamma \vdash ¬(\alpha \rightarrow \alpha) $ for some formula $\alpha$. How to prove that if $ \Gamma $ is inconsistent, then $ \Gamma \vdash \beta $? ...
1
vote
1answer
25 views

negating propositional formula with quantifiers

In order to solve an exercise in computer sciences (proving a language $L$ to not be context-free) I need to negate the Pumping-Lemma. I was provided with the definition in the following form: If $L$ ...
0
votes
1answer
53 views

Proof of a theorem using Hilbert's system

I am trying to prove various theorems considering a Hilbert System. However, i could not find the answer for these three. $\vdash(\alpha \rightarrow \beta) \rightarrow ((¬\alpha\rightarrow\beta)\...
1
vote
1answer
118 views

How Do I Prove the 6 Letter Thesis Cδδ0δp?

There exists a 1951 paper by C. A. Meredith which proves a completeness meta-theorem for the "C, 0, δ, p" system which has as it's sole axiom Cδδ0δp under uniform substitution for propositional ...
0
votes
1answer
39 views

“logical constant” vs “logical variable”

I'm learning introduction to logic on coursera offered by Michael Genesereth with Stanford University, where the the course used the term "logical constant" to denote a proposition sentence. For ...
1
vote
2answers
37 views

precedence problem of multiple implication operators in logics

Should a→b→c be read as (a→b)→c or a→(b→c)? I used a online truth table generator (http://logic.stanford.edu/intrologic/secondary/applications/babbage.html) to test and got a→(b→c) is the ...
0
votes
1answer
15 views

A question on a specific implication, given certain conditions

Is the implication $$A \implies \left(B \oplus C\right)$$ logically equivalent to $$\left(A \implies B\right) \oplus \left(A \implies C\right),$$ where $\oplus$ is the logical XOR operator, and $B$ ...
0
votes
2answers
48 views

Showing that Modus Tollens is sound

When asked to show that Modus Tollens is sound in the propositional calculus, I tried to do this by enumerating all interpretations using a truth table. However I am unsure that my deductions are ...
3
votes
2answers
76 views

Prove $(A\rightarrow C)\land(C\rightarrow\neg B) \land B\rightarrow\neg A$ is valid without using truth tables

just finished proving an argument without the use of truth tables and was wondering if my reasoning is sound. The problem given was Prove using a proof sequence that the argument is valid (hint: ...
-1
votes
2answers
49 views

How to prove semantical equivalence?

Prove that: If $ \alpha \equiv \beta $ and $ \beta \equiv \gamma $ then $ \alpha \equiv \gamma $ I know that: $ \alpha \equiv \beta $ if and only if $ \alpha \leftrightarrow \beta $ is a ...
-1
votes
1answer
52 views

Verifying an equivalence using propositional logic theorems

How to verify the following equivalence: $ \alpha_1 \to \alpha_2 \to ... \to \alpha_n \equiv \alpha_1 \land \alpha_2 \land ... \alpha_{n-1} \to \alpha_n $ How should I use the deduction theorem in ...
1
vote
2answers
45 views

$\def\imp{\Rightarrow}$Proving equivalence of $(P \imp Q) \land (Q \imp P) \equiv (P \lor Q) \imp (P \land Q)$

I am a little stymied by the following: $(P \imp Q) \land (Q \imp P) \equiv (P \lor Q) \imp (P \land Q)$ Working with the RHS I have: $\neg(P \lor Q) \lor (P \land Q) $ $( \neg (P \lor Q) \lor P) ...
3
votes
2answers
50 views

Can a simple (atomic) proposition be a tautology?

Definition: "A tautology is a propositional formula that is true under any truth assignment to each of the atomic propositions in the domain of propositional function." Let $p$ be a simple (or atomic)...
0
votes
1answer
41 views

Proving the equivalence between two congruences.

According to this answer (and the modular arithmetic theory), $ax\equiv ay \pmod{n} \iff x\equiv y \pmod{n}$, if $a$ and $n$ are relatively prime. I tried to prove the forward implication but reached ...
0
votes
1answer
25 views

Universal and Existential quantifier in Propositional logic

The following paragraph is an excerpt from Discrete Mathematics book of Kenneth Rosen 7edition The restriction of a universal quantification is the same as the universal quantification of a ...
0
votes
1answer
29 views

Resolution refutation of a tautology not resolving.

I've been tasked with resolving the following statement to prove that it is valid: $(p\rightarrow q) \rightarrow ((p \lor r) \rightarrow (q \lor r))$ I convert to CNF with the following set of ...
0
votes
0answers
47 views

Proof of propositional logic theorem using Induction on Formulas

How to prove the following theorem using induction on formulas? Let V and V' be two valuations of L. Let $\alpha$ be a formula such that V(p) = V'(p), for all atomic formula p that is subformula ...
0
votes
3answers
31 views

What does negation exactly imply in the following statement(s)?

The professor in my Discrete Mathematics class gave us the following example for the negation of a proposition. A: "All math majors are male" is the proposition. (negation)A: "It is not the case ...
0
votes
1answer
25 views

A lemma for interpolation for propositional logic

I'm working on an exercise for William Craig's Interpolation Theorem for propositional logic, and I'm having troubles proving the following lemma: Let ϕ and ψ be sentences of propositional logic and ...
1
vote
2answers
45 views

Compound propositions as assertions?

According to comments on my previous question, compound propositions are not assertions; i.e. the statement "$p \vee q$" does not mean "$p$ (is true) or $q$ (is true)", and it does not mean "$(p$ or $...
2
votes
1answer
28 views

Can I use negations in the rules of inference?

For example, modus ponens is $p \land (p → q) \therefore q$. If I had $¬p$ and $¬q$, could I do $¬p \land (¬p → ¬q) \therefore ¬q$?
0
votes
1answer
21 views

Set of formulas has no model

I need some help with the following problem. I have to show that the set of formulas $\{\phi_1,\phi_2,\phi_3,\phi_4\}$ has no model, where $$\begin{align*} \phi_1&=\forall x \forall y \forall z (...
5
votes
1answer
62 views

Proof of $(\neg A \supset A) \supset A$

As a (total) beginner in logic, I read this introduction : http://www.loria.fr/~roegel/cours/logique-pdf.pdf (in french). They give an exercise I couldn't achieve. Could someone help me (give an ...
1
vote
0answers
28 views

Number of Minimally Functionally Complete (adequate) ternary Operators Sets and what they are

Is there a simpler way than through trial and error to determine the number of Minimally Functionally Complete Operator Sets (MFCOS) (or adequate operator sets) for a given arity and what those ...
0
votes
1answer
32 views

Would the following series of implications be logically correct?

Let $a$ and $b$ be positive integers, and let $f$ be a generic function satisfying $f(1) = 1$, and taking on only positive integer values. Suppose that I have the following propositions: $$\bf{A} : ...
0
votes
1answer
53 views

p,q are two propositions.It is given that, p ⇒ q is true.Consider the following conclusions,

$ \neg p\rightarrow\neg q$ is true $\neg q\rightarrow\neg p$ is true $p\rightarrow \neg p∨q$ is true Now which one is the correct? and explain this.Thanks!
0
votes
1answer
50 views

The positive introspection axiom

I am studying modal logic with the textbook 'Reasoning about Knowledge' Fagin et al. 1995 The positive introspection axiom is taken as something that can be proved with the possible worlds model of ...
1
vote
2answers
26 views

Should multiple premises of a natural deduction inference rule always have the same context?

Consider the conjunction introduction and implication elimination rules of natural deduction: $$\frac{\Gamma\vdash\alpha \quad \Gamma\vdash\beta}{ \Gamma\vdash \alpha \land \beta} (\land I) \qquad ...
3
votes
1answer
29 views

Notation: When to imply and when to express equivalence?

I have recently been trying to improve the readability of my work as I solve equations, so that I and others can easily navigate how exactly I solved them. I want to make sure I using proper notation. ...
1
vote
2answers
69 views

Is it possible to eliminate a contradiction without recourse to the principle of explosion?

I'd like to derive the following inference rule: $$ \frac{p\lor(q\land\neg q)}{p}\quad\text{[ContradictionElimination]} $$ I assumed that I could do this minimally somehow, however it turns out I ...
1
vote
1answer
37 views

Is there a name for the propositional tautology (and it's associated rule) $Q\Rightarrow(P\Rightarrow Q)$?

I have the tautology $Q\Rightarrow(P\Rightarrow Q)$. I can prove this intuitionistically: ...
0
votes
0answers
47 views

Encoding a graph coloring problem in SAT/CNF for DPLL algorithm

I'm having trouble trying to convert the following problem to SAT for later application to DPLL: Given a connected, undirected graph G, with k colors $\{ c_1 , ..., c_k \} $ and any number of ...
0
votes
2answers
51 views

What exactly is the role of the material conditional in intuitionistic logic?

There seems precious little around about the use of the material conditional in intuitionistic logic aside from the Wikipedia page https://en.wikipedia.org/wiki/Material_conditional and I can't seem ...
2
votes
1answer
49 views

Is double negation introduction an axiom of intuitionistic logic or can it be derived?

If I have a rule for negation introduction... Rule (NegationIntroduction,ProofByNegation) Premises P=>Q, P=>⌐Q Conclusion ⌐P ...then it seems ...
0
votes
0answers
14 views

Propositional logic for a proof

I was able to prove the following proposition Suppose that $x > 0$ and that $y \in [0, 1] \cap S_x$. Then $$y \in [c(x), d(x)],$$ where $c(x)$ and $d(x)$ are two particular real valued ...
0
votes
2answers
42 views

Proving existence of a wff that is logically equivalent to a wff given some conditions

For convenience, let us define a wff to be positive if there is no use of the negation symbol $\neg$ at all in the wff. Hence, for example, $W=P\iff Q$ is a positive wff. Now the question is to show ...
3
votes
2answers
61 views

How to prove that $(p\rightarrow q)\wedge(p\rightarrow r)$ and $p\rightarrow (q \wedge r)$ are logically equivalent?

I am trying to prove that $(p\rightarrow q)\wedge (p\rightarrow r) = p\rightarrow (q \wedge r)$. This is my approach: $(p\rightarrow q)\wedge(p\rightarrow r) = (-p \vee q) \wedge (-p \vee r)$ = ${[...
1
vote
2answers
51 views

How does the axiom schema of replacement work?

According to this website, the first partion of this axiom schema is Let $P(y,z)$ be a propositional function, which determines a function. That is, we have $∀y(∃x:(∀z:(P(y,z)⟺(x=z))))$. ...
1
vote
2answers
27 views

Is this conclusion via rules of inference correct?

Use rules of inference to show: ∀x(P(x) → Q(x)) premise ∀x(Q(x) → R(x)) premise ¬R(a) premise ¬P(a) conclusion I have a lot of trouble with these sort of questions and was wondering if I did this ...