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)

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
23 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
103 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
28 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
114 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
65 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
89 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
25 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
45 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
33 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
35 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
65 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
28 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
71 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
34 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
40 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
33 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
38 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 ...
0
votes
1answer
22 views

Logic Proof using Inference rules and replacement rules

I am trying to prove the following using the inference and replacement rules in logic: (A . F) ⊃ (C ∨ G), ~ (C ∨ (F . G)), F ≡ ~ (X . Y), ~ (X ∨ ~ W) /∴ ~ (A ∨ X) I have this so far: Work But I do ...
0
votes
0answers
27 views

Proving theorems using the Compactness theorem

We say an infinite set $S$ is closed under $\wedge$ if for all $a,b$ $\in S$ so $a\wedge b \in S$. I need to prove that if S is closed under $\wedge$ and for all $a \in S$ we know is that $a$ is ...
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 ...
1
vote
0answers
33 views

Natural Deduction Proof $\neg(P \to Q) \vdash Q \to P$

I am trying to answer Question 3(e) in Exercise 1.2 of Huth and Ryan's Logic in Computer Science book for revision and I am stuck on it. The question asks you to prove the validity of the following ...
1
vote
0answers
16 views

Logic - logical connective for (~ABC) + (A~BC) + (AB~C)?

Is there a logical connective that says 'True, if and only if 1 proposition is true'. Or perhaps even better, is there one that describes 'True, if and only if n propositions is true'? Where n is an ...
1
vote
2answers
27 views

Commas in propositional logic

I want to know what effect a comma has on a propositional statement. For example: $\{\neg p, p \vee q \} \vDash q$ Does this bit $\{\neg p, p \vee q \}$ mean just $q$? Thanks.
2
votes
3answers
72 views

Logical limitations of Proofs by Contradiction

In general proofs by contradiction go as follows: Given an arbitrary hypothesis, $\ p \implies q$, we assume $\left(p\implies q\right) = T$, and then we show that by assuming the hypothesis to be ...
0
votes
1answer
10 views

How to eliminate bi conditionals?

p <--> q can be written as (p → q) ∧ (q → p) (~p V q) Λ (~q V p) After this I am confused. If I distribute Λ over V, I get (~p V q Λ ~q) V (~p V q Λ p) which becomes (~p V q Λ ~q ) V (~p V q ...
1
vote
2answers
72 views

Deducing $((\neg a \to \neg b) \to ((\neg a \to b) \to b)))$ from axioms

I have seen many questions here, using a different set of axioms than mine. Here is mine : $$1) (a \to (b \to a))$$ $$2) ((a \to (b \to c)) \to ((a \to b) \to (a \to c)))$$ $$3) ((\neg b \to \neg a) ...
2
votes
2answers
36 views

Propositional calculus axiom the other way around

I have the following axioms of propositional calculus (as well as modus ponens and the deduction theorem if needed): $$(a \to (b \to a)) \tag1$$ $$ (((a \to (b \to c)) \to ((a \to b) \to (a \to c))) \...
4
votes
1answer
154 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
1answer
44 views

Tarski's schema T

On Wikipedia, Tarski schema T says: A sentence of the form "A and B" is true if and only if A is true and B is true A sentence of the form "A or B" is true if and only if A is true or B is true A ...
0
votes
2answers
48 views

Prove $[(P \lor A) \land ( \neg P \lor B)]\rightarrow (A \lor B)$

I want to prove that $[(P \lor A) \land ( \neg P \lor B)] \rightarrow (A \lor B)$, using distributions or reductions (even though I am aware that simpler proofs exist). The issue is that I keep ...
2
votes
1answer
69 views

Generators of the Lindenbaum-Tarski algebra

I am a bit confused about the role of propositional variables in the construction of the free Lindenbaum-Tarski algebra. In the entry "Lindenbaum-Tarski algebra" on Wikipedia, in the section "...
0
votes
1answer
46 views

Is there a blackboard bold letter for the set of Boolean numbers? [duplicate]

Is there a symbol (e.g. $\mathbb{B}$) for the special set of Boolean numbers or values; ${0,1}$ or ${True,False}$?
0
votes
0answers
17 views

Mathematical logic: Predicates, formula

I've got universum $A = \{0,1,2\}$ Predicate: $R^{A}=\{\{x,y\} \in A \times A \hspace{2mm} | \hspace{2mm} x \neq y \} $ Terms: $f^A(x) = 1$ $g^A(x,y) = min(x,y)$ Constant $c^A = 2$ Valuation: $...
2
votes
0answers
67 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
1answer
32 views

Prove or disprove in propositional calculus

I have the following question - and would like to make clear some definition via it's answer - Prove of Disprove - If $\\X\models\alpha$ and $\\Y\models\alpha$, then $X\cap Y\models\alpha$ ...
1
vote
0answers
20 views

From Propositional Calculus Proof to Predicate Calculus Proof

PROVE: If {$\Delta_{i}$} are all deductively closed set of formulae, so is $\cap \Delta_i$. Show with predicate Calculus. Definition: {$\Delta_{i}$} a set $\Delta$ of formulae is deductively closed ...
3
votes
0answers
41 views

Strict order on propositions and interpolation

We can define a strict order on the set of propositions in countably many propositional letters in the following way: $$\varphi\sqsubset\psi \iff (\models \varphi\rightarrow\psi)\, \land (\not\models ...
0
votes
4answers
94 views

Why is “$A$ unless $B$” equivalent to $A \lor B$?

$A$ unless $B$ surely means, 'given that $B$ does not happen, $A$ will happen'. So if $B$ happens, $A$ does not happen. Yet I've read, by those officially accredited, that $A$ unless $B$ = $A$ or $B$...