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)

1
vote
0answers
19 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
20 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
57 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
22 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
31 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
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
47 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 ...
-5
votes
1answer
61 views

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

This is the puzzle I am having trouble in understanding Also, do explain me the question along with the answer. Thank You
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 ...
4
votes
1answer
27 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
65 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
36 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
47 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
40 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
60 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
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 ...
3
votes
1answer
91 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 ...
1
vote
4answers
114 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. ...
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
3answers
63 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
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 ...
0
votes
1answer
26 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
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 ...
1
vote
1answer
64 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 ...
1
vote
1answer
65 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
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) ...
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 ...
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
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
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
33 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
3answers
63 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
61 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 ...
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)$ ...
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 ...
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 ...
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 ...
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 ...
1
vote
2answers
30 views

Can a propositional function have quantifiers?

According to Wikipedia, an open formula is a WFF without quantifiers. I have read that a propositional function is the same as open formula. Are both of these statements correct? Is it true that ...
1
vote
1answer
43 views

Describe 3-colourable graph in propositional calculus

I am trying to solve the following problem. Let $G=(V,E)$ be a Graph with $V=N$ (natural numbers) and $p_{ij}$ a set of propositional variables for which we have $p_{ij}$ is true <=> $(i,j)\in E$. ...
0
votes
1answer
20 views

Natural Deduction Proof (c ∧ n) → t, h ∧ ¬s, h ∧ ¬(s ∨ c) → p |− (n ∧ ¬t) → p

I'm trying to do a question from Huth and Ryan's book 'Logic in Computer Science' and I am stuck on the following natural deduction proof: prove by natural deduction that the sequent (c ∧ n) → t, h ∧...
0
votes
1answer
37 views

What are the roots of propositional logic?

You know, I actually started learning about propositional logic by asking the same question, but about maths. However, now am wondering what the roots are of propositional logic, I mean, we don't ...
1
vote
1answer
19 views

Understanding predicate logic given symbolic notation?

I'm having trouble understanding predicate logic. Question J is that saying "All broken windows are in the garage"? Is K. saying "for every x in the garage the x has a broken window" L.) "there ...