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
1answer
25 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} : ...
1
vote
2answers
346 views

Prove $( \lnot C \implies \lnot B) \implies (B \implies C)$ without the Deduction Theorem

The issue is Exercise 1.47 (d) in Elliot Mendelson's "Mathematical Logic". The exercise is to prove $(\lnot C\implies\lnot B)\implies(B\implies C)$ by using the three axioms $(A1,A2,A3)$ without using ...
0
votes
1answer
848 views

Disjunctive normal form (BOTH dnf and cnf) example help

T or ( not x and y ) or ( x and y ) In class we went over examples of how many things can be both DNF and CNF... eg. (not z) or y can be thought of as both (not z) or y .... dnf ((not z) or y)...
0
votes
1answer
52 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
46 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 ...
-5
votes
1answer
57 views

What would be the solution to this logic puzzle? [on hold]

This is the puzzle I am having trouble in understanding Also, do explain me the question along with the answer. Thank You
4
votes
1answer
26 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
62 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 ...
0
votes
2answers
621 views

Solving Logical equivalence & propositional logic problems without truth tables

I have no particular "Logic question" in hand at the time being, but need help to understand a way that can be used to prove "Logical equivalence without using truth tables". moreover can we solve ...
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 ...
0
votes
0answers
29 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 ...
2
votes
1answer
46 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
2answers
39 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 ...
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 ...
3
votes
2answers
59 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
49 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
1answer
63 views

Are standalone statements conventionally considered to imply truth?

From what I understand, the statement $\exists x(p(x) \vee q(x))$ in the English language sounds something like this: "There exists $x$ such that $p(x)$ or $q(x)$". But this sounds like an incomplete ...
0
votes
1answer
1k views

Expressing the converse, contra-positive, and inverse of conditional statements

This problem is from Discrete Mathematics and its Applications Here is my book's definition on converse, contrapositive, and inverse And the common ways to express an implication For this ...
1
vote
3answers
62 views

alternative rule for negation introduction

I have the standard rule for negation introduction, namely: $$\frac{P\Rightarrow Q\quad P\Rightarrow\neg Q}{\neg P}\quad\text{[Proof by negation]}$$ Now I need a slightly different rule (I'm not ...
1
vote
2answers
26 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 ...
0
votes
2answers
37 views

About a proof of the Adequacy of Natural Deduction for Propositional Logic

In Mathematical Logic by Chiswell and Hodges, section 3.10 page 89 proves the following theorem: Theorem 3.10.1 (Adequacy of Natural Deduction for Propositional Logic) Let $\Gamma$ be a set ...
4
votes
1answer
152 views

When does the dual of $s =s$?

Why I believe this is not a duplicate: This question might be the same, but the accepted answer is only a partial answer, because it gives no reason as to why those are the only solutions. Since the ...
1
vote
4answers
110 views

A tough logic puzzle

I took a course on logic a few semesters ago so am having trouble remembering certian concepts. I came across another problem in one of my classes yesterday and am not sure how to solve it exactly. ...
3
votes
1answer
90 views

Formalizing splitting into cases

Let $x$ denote a fixed but arbitrary real, and suppose we're trying to solve an equation like $$(x^2-1)^2 = 1.$$ The 'high school' approach is to just shuffle the functions on one side onto the other ...
3
votes
3answers
60 views

Truth Table - implies false

I'm work with a task where I am not exactly sure if I proceed right. The task is saying: "We define the operation $\oplus$ by $a \oplus b = (a \wedge \neg b) \vee (\neg a \wedge b)$. Give the truth ...
0
votes
0answers
22 views

Composition of substitutions of SLD tree

I found a question on my university past paper and it asked to get the SLD tree from a computation rule using some rules and facts. However I obtained the answer and to complete the question I have to ...
1
vote
1answer
101 views

Propositional Logic. Ice cream Maze

I am stuck with this problem. I know I have to use propositional logic and truth tables, but I believe that in order to be sure about the right way to get to the Cold Stone Creamery I need to get a ...
1
vote
0answers
113 views

Green eyes/Common Knowledge problem proof verification

I was trying to solve the common knowledge problem, but am not sure if my proof is accurate. Here is a rough statement of the problem : 'An island consists of $k$ people with green eyes, all ...
0
votes
1answer
25 views

Prove tautology using truth trees

Hi there I have to prove some tautologies using truth trees. I am doing this by negating the expresion and then trying to find contradictions on every branch. But I can't achieve this. I can't find ...
1
vote
1answer
63 views

Can we logically analyze mathematical theorems as if-then statements?

Many theorems in math have an if-then form. For example: "If a polynomial is of $n^{th}$ degree, then it has $n$ roots. In my other question, I learned that in order to analyze statements using truth ...
4
votes
4answers
151 views

Difficulty understanding why $ P \implies Q$ is equivalent to P only if Q.

I have difficulties understanding why $ P \implies Q$ is equivalent to P only if Q. I do understand that in the statement "P only if Q", it means if $ \lnot Q \implies \lnot P$". Regarding this ...
0
votes
3answers
17 views

Propositional statements dealing with “only if”

If I have the statement. "I can ride my bike only if tires aren't broken" and I have P(X) = "I can ride my bike" and I have Q(X) = "My tires are broken" Would the above statement be P -> Not(Q) ...
1
vote
2answers
43 views

How to generalize the principle of mathematical induction for proving statements about more than one natural number?

Suppose that $P(n_1, n_2, \ldots, n_N)$ be a proposition function involving $N >1$ positive integral variables $n_1, n_2, \ldots, n_N$. Then how to generalise the familiar induction to prove this ...
0
votes
0answers
21 views

Prove or disprove a FOL sentence using relevant domain diagrams: $\exists x (a.x\to b.x) \to (\forall x\,\, ax \to \exists b.x)$

Prove or disprove the FOL sentence using relevant domain diagrams: $$\exists x (a.x\to b.x) \to (\forall x\,\, a.x \to \exists x\, b.x)$$ Can you suggest me a way to prove or disprove above two ...
0
votes
1answer
26 views

Why is $P(x)$ allowed to have other variables than $x$ free?

Using the common definition of a propositional function $P(x)$ as "a WFF which would be either true or false were it not for a variable $x$, with other variables also allowed to be free". For example,...
0
votes
3answers
60 views

Propositional Logic - Can you Derive $C \to A$ from $A$ alone, given the introduction rule?

Apparently, according to the Conditional Introduction rule, this is valid: Prove $C \to A$ Source: http://kpaprzycka.wdfiles.com/local--files/logic/W12R Page 5 So before this, the way I viewed ...
2
votes
2answers
58 views

Logic - What does a half T mean in logic?

TLDR nevermind I'll include a screenshot; I've looked for the symbol everywhere, it wasn't even found via wikipedia: https://en.wikipedia.org/wiki/List_of_logic_symbols It also wasn't in the list of ...
3
votes
1answer
88 views

Why are Duals of Two Equivalent compound propositions Equivalent?

I know that if we have two equivalent propositions p and q then p* and q* will also be equivalent where p* and q* are duals of p and q respectively. I am looking for some explanation to why duals of ...
0
votes
2answers
32 views

How to simplify this logical expression?

Using logical laws, I would like to simplify the following expression: $\neg a \lor \neg b \lor (a \wedge b \wedge \neg c)$ 1) Distribution law: $(\neg a \lor a) \land (\neg a \lor b) \land (\neg ...
1
vote
0answers
32 views

Consistency Lemma in Lindenbaum's Theorem

Let $\Lambda$ be a modal logic, we say that a formula $\varphi$ is $\Lambda$-inconsistent if $\vdash_\Lambda (\neg \varphi)$ and is consistent otherwise. Similarly we say that a set of modal formulas $...
0
votes
0answers
41 views

Propositional formulas for connected graph

I have some difficulties with the following problem. Let $G = (V,E)$ be a graph with $V = \mathbb N$ (natural numbers) and $E \subset \mathbb N^2$. Let $p_{ij}$ be a set of propositional ...
0
votes
0answers
26 views

Simplifying logical expression using logical laws

I simplified the logical expression: $(z \land w) \lor (\lnot z \land w) \lor (z \land \lnot w)$ using logical laws following these steps: 1) Absorption Law: $(z \land w) \lor (\lnot z \land w)$ ...
0
votes
1answer
47 views

How to know the contrapositive of a compound logical expression?

In simple expressions like: $p \implies q $ the contrapositive would be: $\lnot q \implies \lnot p$. But in other cases where the expression gets more complex: ($p \land q) \implies (\lnot q \lor p)$. ...
1
vote
1answer
32 views

Stuck at one step on the proof of distributive law of implication over disjunction

I'm working with classic natural deduction system NK and the elimination rule for disjunction is stated as follows (I apologize, I don't know how to express it in tree-form): $\Gamma \vdash \chi$ is ...
4
votes
1answer
69 views

How many equivalence classes are there under the relation of logical equivalence?

I was wondering how might one go about solving the question: How many different last columns occur among all the truth tables with propositional variables p, q, r, s? (In other words, how many ...
2
votes
0answers
66 views

Are these two logical statements equal?

I found this question from a website: "Neither the fox nor the lynx can catch the hare if the hare is alert and quick." Let: P: The fox can catch the hare Q: The lynx can catch ...
0
votes
2answers
36 views

Is my translation of unless into propositional logic correct?

I have the following sentences: I won't go the library unless I need a book p: I will go the library q: I need a book I replaced unless with if not as follows: I won't go the library ...
1
vote
1answer
155 views

Is ({1, 0}, ⊕, ∨) a field? and Is ({1, 0}, ⊕, ∧) a field?

1 and 0 denote the logical statements True and False. These two questions are for homework so would rather an answer that could help explain it to me then just a straight answer. Thanks to anyone who ...