[pt] Segerberg apresentou uma prova geral da completude para lógicas proposicionais. Para tal, um sistema de dedução foi definido de forma que suas regras sejam regras para um operador booleano arbitrário para uma dada lógica proposicional. Cada regra desse sistema corresponde a uma linha na tabela de verdade desse operador. Na primeira parte desse trabalho, mostramos uma extensão da ideia de Segerberg para lógicas proposicionais finito-valoradas e para lógicas não-determinísticas. Mantemos a ideia de definir um sistema de dedução cujas regras correspondam a linhas de tabelas verdade, mas ao invés de termos um tipo de regra para cada valor de verdade da lógica correspondente, usamos uma representação bivalente que usa a técnica de fórmulas separadoras definidas por Carlos Caleiro e João Marcos. O sistema definido possui tantas regras que pode ser difícil trabalhar com elas. Acreditamos que um sistema de cálculo de sequentes definido de forma análoga poderia ser mais intuitivo. Motivados por essa observação, a segunda parte dessa tese é dedicada à definição de uma tradução entre cálculo de sequentes e dedução natural, onde procuramos definir uma bijeção melhor do que as já existentes. / [en] Segerberg presented a general completeness proof for propositional logics. For this purpose, a Natural Deduction system was defined in a way that its rules were rules for an arbitrary boolean operator in a given propositional logic. Each of those rules corresponds to a row on the operator s truth-table. In the first part of this thesis we extend Segerbergs idea to finite-valued propositional logic and to non-deterministic logic. We maintain the idea of defining a deductive system whose rules correspond to rows of truth-tables, but instead of having n types of rules (one for each truth-value), we use a bivalent representation that makes use of the technique of separating formulas as defined by Carlos Caleiro and João Marcos. The system defined has so many rules it might be laborious to work with it. We believe that a sequent calculus system defined in a similar way would be more intuitive. Motivated by this observation, in the second part of this thesis we work out translations between Sequent Calculus and Natural Deduction, searching for a better bijective relationship than those already existing.

本研究採用分層叢集抽樣，從台北市十二行政區中，按比例抽出36所學校。受試者含1-9年級學生合計5475人，有效樣本4917人達89.8%。自編測驗信度、效度考驗：α係數達.80，效標關連效度在.21到.70之間，與智力測驗之相關在各年級均達.01顯著水準，專家效度良好。研究發現包括二部份： 一、邏輯概念之發展：有關台北市立國民中小學學生邏輯概念發展狀況研究結果如次 (1) 形式運思階段之前，兒童可以解答部份的命題邏輯問題。 (2) 具體內容的ＭＰ規則和常見的遞移性關係的遞移推理，分別在國小一年級、及國小四年級已達到發展高原。 (3) 從具體運思到形式運思階段，並沒有發現階段性跳躍的成長現象，邏輯概念發展大致上是向上發展的型態。 (4) 二元運算系統在8,9年級(14、15歲左右)--也就是皮亞傑所指的形式運思階段達到平衡的時期，只能做大約18%?32%的題目，沒有證據顯示大部份的受試者，已經完成了具有「群與格」特徵的命題邏輯結構。本研究的假設一、假設二均未獲得支持。皮亞傑理論對學生的邏輯概念發展有低估和高估的現象。一方面低估了國小中低年級兒童在簡單邏輯規則的發展，另一方面高估了青少年在困難的邏輯規則上所能達到的成就。 二、邏輯概念與數學之相關性：在邏輯與數學的相關性研究方面獲得以下結論： (1) 邏輯成績與數學成績的相關在各年級學生中，均達.0001顯著水準。大部份年級數學成績與智力的相關，大於數學成績與邏輯概念的相關。 (2) 年級對邏輯概念的影響效果顯著，當控制智力高低及數學成就好壞二個因素之後，邏輯概念隨年級而增進。 (3) 數學成就對邏輯概念的影響效果顯著，對各年級學生而言，高數學成就組學生的邏輯概念比其他二組好。但數學成就中等和低等的二組受試者之間，當智力的百分等級在35?56之間時，邏輯概念沒有差異。 (4) 變異數分析顯示，以年級、數學成就與智力的線性模式，可以解釋邏輯概念所有變異量中的63%。共變異數分析顯示，排除智力的影響之後，年級、數學成就仍是可以解釋邏輯概念所有變異量中的63%，與變異數分析結果一致。

This thesis focuses on improving the SAT solving technology. The improvements focus on two major subjects: sequential SAT solving and parallel SAT solving. To better understand sequential SAT algorithms, the abstract reduction system Generic CDCL is introduced. With Generic CDCL, the soundness of solving techniques can be modeled. Next, the conflict driven clause learning algorithm is extended with the three techniques local look-ahead, local probing and all UIP learning that allow more global reasoning during search. These techniques improve the performance of the sequential SAT solver Riss. Then, the formula simplification techniques bounded variable addition, covered literal elimination and an advanced cardinality constraint extraction are introduced. By using these techniques, the reasoning of the overall SAT solving tool chain becomes stronger than plain resolution. When using these three techniques in the formula simplification tool Coprocessor before using Riss to solve a formula, the performance can be improved further. Due to the increasing number of cores in CPUs, the scalable parallel SAT solving approach iterative partitioning has been implemented in Pcasso for the multi-core architecture. Related work on parallel SAT solving has been studied to extract main ideas that can improve Pcasso. Besides parallel formula simplification with bounded variable elimination, the major extension is the extended clause sharing level based clause tagging, which builds the basis for conflict driven node killing. The latter allows to better identify unsatisfiable search space partitions. Another improvement is to combine scattering and look-ahead as a superior search space partitioning function. In combination with Coprocessor, the introduced extensions increase the performance of the parallel solver Pcasso. The implemented system turns out to be scalable for the multi-core architecture. Hence iterative partitioning is interesting for future parallel SAT solvers. The implemented solvers participated in international SAT competitions. In 2013 and 2014 Pcasso showed a good performance. Riss in combination with Copro- cessor won several first, second and third prices, including two Kurt-Gödel-Medals. Hence, the introduced algorithms improved modern SAT solving technology.

In classical propositional logic (CPL) logical reasoning is formalised as logical entailment and can be computed by means of tableau and resolution proof procedures. Unfortunately CPL is not expressive enough and using first order logic (FOL) does not solve the problem either since proof procedures for these logics are not decidable. Modal propositional logics (MPL) on the other hand are both decidable and more expressive than CPL. It therefore seems reasonable to apply tableau and resolution proof systems to MPL in order to compute logical entailment in MPL. Although some of the principles in CPL are present in MPL, there are complexities in MPL that are not present in CPL. Tableau and resolution proof systems which address these issues and others will be surveyed here. In particular the work of Abadi & Manna (1986), Chan (1987), del Cerro & Herzig (1988), Fitting (1983, 1990) and Gore (1995) will be reviewed. / Computing / M. Sc. (Computer Science)

This work describes graphplan, satplan and real-time adaptive A* planning algorithms. Through implementation of these algorithms, functionality and assumed attributes (real-time calculation, parallelism) are tested. These tests take place in nontrivial domains. Graphplan and satplan algorithms were tested in block-world, tire-world and bulldozer domains. Results of these tests were compared and displayed in graphs. Real-time adaptive A* algorithm was tested in tire-world domain. Results of these tests were compared with classic A* algorithm. Advantages and disadvantages of these algorithms are also described in this work.

Die Arbeit umfasst eine Explikation des Algorithmus Begriffes, die Angabe einiger Algorithmen zur Beantwortung von Fragestellungen im Bereich der Aussagenlogik sowie Beweise für das Genügen angegebener Algorithmen bezüglich der gegebenen Explikation des Algorithmus Begriffes und für die Korrektheit der Algorithmen hinsichtlich der Beantwortung der entsprechenden Fragestellungen im Bereich der Aussagenlogik. / The thesis contains an explication of the concept of algorithm, specification of a few algorithms regarding answering questions in the field of propositional logic as well as proofs for the satisfaction of the given algorithms concerning given explication of the concept of algorithm and for the correctnes of the given algorithms respective answering the corresponding questions in the field of propositional logic.

This thesis focuses on improving the SAT solving technology. The improvements focus on two major subjects: sequential SAT solving and parallel SAT solving. To better understand sequential SAT algorithms, the abstract reduction system Generic CDCL is introduced. With Generic CDCL, the soundness of solving techniques can be modeled. Next, the conflict driven clause learning algorithm is extended with the three techniques local look-ahead, local probing and all UIP learning that allow more global reasoning during search. These techniques improve the performance of the sequential SAT solver Riss. Then, the formula simplification techniques bounded variable addition, covered literal elimination and an advanced cardinality constraint extraction are introduced. By using these techniques, the reasoning of the overall SAT solving tool chain becomes stronger than plain resolution. When using these three techniques in the formula simplification tool Coprocessor before using Riss to solve a formula, the performance can be improved further. Due to the increasing number of cores in CPUs, the scalable parallel SAT solving approach iterative partitioning has been implemented in Pcasso for the multi-core architecture. Related work on parallel SAT solving has been studied to extract main ideas that can improve Pcasso. Besides parallel formula simplification with bounded variable elimination, the major extension is the extended clause sharing level based clause tagging, which builds the basis for conflict driven node killing. The latter allows to better identify unsatisfiable search space partitions. Another improvement is to combine scattering and look-ahead as a superior search space partitioning function. In combination with Coprocessor, the introduced extensions increase the performance of the parallel solver Pcasso. The implemented system turns out to be scalable for the multi-core architecture. Hence iterative partitioning is interesting for future parallel SAT solvers. The implemented solvers participated in international SAT competitions. In 2013 and 2014 Pcasso showed a good performance. Riss in combination with Copro- cessor won several first, second and third prices, including two Kurt-Gödel-Medals. Hence, the introduced algorithms improved modern SAT solving technology.