Introduction à la logique informatique - Partie 1 : calcul propositionnel

بواسطة: France Université Numerique

Overview

À propos de ce cours

La logique servait surtout la philosophie et la théologie jusqu'au 19ème siècle. Elle est apparue de manière brutale et cruciale au tournant du 20ème siècle en mathématiques, avec les paradoxes et la question des fondements. Après le théorème de Gödel et la faillite du programme de Hilbert, la logique mathématique est devenue une partie spécialisée des mathématiques pures. Mais l'âge d'or de la logique arrive ensuite avec le développement de l'informatique.

L'utilisation des ordinateurs a forcé à formaliser complètement les problèmes à résoudre; la logique joue un rôle central dans les problèmes de spécification et de vérification des programmes. Du fait d'un lien surprenant entre les preuves et les programmes, la logique est aussi la base de la compréhension des calculs. Plus concrètement, la logique a été à l'origine d'avancées technologiques comme les langages de requêtes dans les bases de données. Beaucoup d'autres liens fondamentaux peuvent être évoqués: avec les circuits, avec la complexité, avec les jeux, avec la linguistique, etc. La logique est omniprésente en informatique.

Le cours présentera les bases de la logique informatique: cette première partie traitera de calcul propositionnel; une seconde partie, à venir, abordera la logique du premier ordre. Un perroquet menteur et des problèmes de pavage nous permettrons d'introduire plusieurs interprétations des formules, et plusieurs systèmes de preuve formelle... et le entscheindungsproblem!

Syllabus

Plan du cours

Ce cours comportera à terme trois parties. Cette première partie, traitera de calcul propositionnel. La seconde partie portera sur la logique du premier ordre, et la troisième sur les théories axiomatiques.

Semaine 1: calcul propositionnel classique

  1. introduction du cours
  2. syntaxe
  3. sémantique
  4. satifaisabilité
  5. Entscheidungsproblem

Semaine 2: compacité et forme clausale

  1. théorème de compacité
  2. forme clausale

Semaine 3: résolution

  1. un système de preuve: la résolution
  2. correction
  3. complétude réfutationnelle
  4. complétude

Semaine 4: logique intuitionniste

  1. sémantique: structures de Kripke
  2. un système de preuve: le calcul des séquents LJ

Semaine 5: correction et complétude de LJ

  1. correction
  2. complétude

Semaine 6: perspectives

  1. calcul des séquents classique
  2. correspondance preuve-programme
  3. conclusion: quelques autres développements possibles

Taught by

Hubert Comon

Introduction à la logique informatique - Partie 1 : calcul propositionnel
الذهاب الي الدورة

Introduction à la logique informatique - Partie 1 : calcul propositionnel

بواسطة: France Université Numerique

  • France Université Numerique
  • مجانية
  • French
  • متاح شهادة
  • أيام محددة
  • الجميع
  • N/A
8.1.2PHP Version352msRequest Duration2MBMemory UsageGET ar/الدورات/{slug}Route
    • Booting (229ms)
    • Application (122ms)
    • 1 x Booting (64.99%)
      228.88ms
      1 x Application (34.78%)
      122.46ms
      14 templates were rendered
      • public.courses.show (resources/views/public/courses/show.blade.php)3bladefile
        Params
        0
        course
        1
        links
        2
        config
      • public.courses.partials.breadcrumbs (resources/views/public/courses/partials/breadcrumbs.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.courses.partials.heading (resources/views/public/courses/partials/heading.blade.php)7bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
        6
        classes
      • public.courses.partials.details (resources/views/public/courses/partials/details.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.courses.partials.breadcrumbs (resources/views/public/courses/partials/breadcrumbs.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.courses.partials.heading (resources/views/public/courses/partials/heading.blade.php)7bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
        6
        classes
      • public.layouts.main (resources/views/public/layouts/main.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.layouts.partials.meta (resources/views/public/layouts/partials/meta.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.layouts.partials.navbar (resources/views/public/layouts/partials/navbar.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.auth.profile.partials.links (resources/views/public/auth/profile/partials/links.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      • public.auth.profile.partials.link (resources/views/public/auth/profile/partials/link.blade.php)8bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
        6
        route
        7
        title
      • public.auth.profile.partials.link (resources/views/public/auth/profile/partials/link.blade.php)8bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
        6
        route
        7
        title
      • public.auth.profile.partials.link (resources/views/public/auth/profile/partials/link.blade.php)8bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
        6
        route
        7
        title
      • public.layouts.partials.flash-session (resources/views/public/layouts/partials/flash-session.blade.php)6bladefile
        Params
        0
        __env
        1
        app
        2
        errors
        3
        course
        4
        links
        5
        config
      uri
      GET ar/الدورات/{slug}
      middleware
      web, localize:ar
      controller
      App\Http\Controllers\CourseController@show
      as
      ar.courses.show
      namespace
      prefix
      /ar
      where
      file
      app/Http/Controllers/CourseController.php:17-35
      7 statements were executed7.57ms
      • select * from `courses` where `slug_ar` = 'introduction-à-la-logique-informatique---partie-1-:-calcul-propositionnel' limit 1
        6.26ms/app/Http/Controllers/CourseController.php:20corspedia
        Metadata
        Bindings
        • 0. introduction-à-la-logique-informatique---partie-1-:-calcul-propositionnel
        Backtrace
        • 17. /app/Http/Controllers/CourseController.php:20
        • 18. /vendor/laravel/framework/src/Illuminate/Routing/Controller.php:54
        • 19. /vendor/laravel/framework/src/Illuminate/Routing/ControllerDispatcher.php:43
        • 20. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:260
        • 21. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:205
      • update `courses` set `visitors` = `visitors` + 1, `courses`.`updated_at` = '2025-02-22 14:36:24' where `id` = 3309
        310μs/app/Http/Controllers/CourseController.php:21corspedia
        Metadata
        Bindings
        • 0. 2025-02-22 14:36:24
        • 1. 3309
        Backtrace
        • 17. /app/Http/Controllers/CourseController.php:21
        • 18. /vendor/laravel/framework/src/Illuminate/Routing/Controller.php:54
        • 19. /vendor/laravel/framework/src/Illuminate/Routing/ControllerDispatcher.php:43
        • 20. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:260
        • 21. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:205
      • select `id`, `name_en`, `name_ar`, `topic_id`, `slug_en`, `slug_ar` from `subjects` where `subjects`.`id` in (6)
        190μs/app/Http/Controllers/CourseController.php:23corspedia
        Metadata
        Backtrace
        • 20. /app/Http/Controllers/CourseController.php:23
        • 21. /vendor/laravel/framework/src/Illuminate/Routing/Controller.php:54
        • 22. /vendor/laravel/framework/src/Illuminate/Routing/ControllerDispatcher.php:43
        • 23. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:260
        • 24. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:205
      • select `id`, `name_en`, `name_ar`, `slug_en`, `slug_ar` from `topics` where `topics`.`id` in (1)
        170μs/app/Http/Controllers/CourseController.php:23corspedia
        Metadata
        Backtrace
        • 25. /app/Http/Controllers/CourseController.php:23
        • 26. /vendor/laravel/framework/src/Illuminate/Routing/Controller.php:54
        • 27. /vendor/laravel/framework/src/Illuminate/Routing/ControllerDispatcher.php:43
        • 28. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:260
        • 29. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:205
      • select * from `institutions` where `institutions`.`id` in (132) and `institutions`.`deleted_at` is null
        220μs/app/Http/Controllers/CourseController.php:23corspedia
        Metadata
        Backtrace
        • 20. /app/Http/Controllers/CourseController.php:23
        • 21. /vendor/laravel/framework/src/Illuminate/Routing/Controller.php:54
        • 22. /vendor/laravel/framework/src/Illuminate/Routing/ControllerDispatcher.php:43
        • 23. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:260
        • 24. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:205
      • select * from `providers` where `providers`.`id` in (47) and `providers`.`deleted_at` is null
        200μs/app/Http/Controllers/CourseController.php:23corspedia
        Metadata
        Backtrace
        • 20. /app/Http/Controllers/CourseController.php:23
        • 21. /vendor/laravel/framework/src/Illuminate/Routing/Controller.php:54
        • 22. /vendor/laravel/framework/src/Illuminate/Routing/ControllerDispatcher.php:43
        • 23. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:260
        • 24. /vendor/laravel/framework/src/Illuminate/Routing/Route.php:205
      • select * from `html_files` where `html_files`.`id` = 3300 limit 1
        220μs/app/Models/Course.php:84corspedia
        Metadata
        Bindings
        • 0. 3300
        Backtrace
        • 21. /app/Models/Course.php:84
        • 28. view::public.courses.show:29
        • 30. /vendor/laravel/framework/src/Illuminate/Filesystem/Filesystem.php:125
        • 31. /vendor/laravel/framework/src/Illuminate/View/Engines/PhpEngine.php:58
        • 32. /vendor/laravel/framework/src/Illuminate/View/Engines/CompilerEngine.php:72
      App\Models\HtmlFile
      1
      App\Models\Provider
      1
      App\Models\Institution
      1
      App\Models\Topic
      1
      App\Models\Subject
      1
      App\Models\Course
      1
        _token
        HTbc2UyW0Zh3RguMIrSiohKVAUOn1OL22q7vuCfb
        locale
        ar
        _previous
        array:1 [ "url" => "https://www.corspedia.com/ar/%D8%A7%D9%84%D8%AF%D9%88%D8%B1%D8%A7%D8%AA/introd...
        _flash
        array:2 [ "old" => [] "new" => [] ]
        PHPDEBUGBAR_STACK_DATA
        []
        path_info
        /ar/%D8%A7%D9%84%D8%AF%D9%88%D8%B1%D8%A7%D8%AA/introduction-%C3%A0-la-logique-informatique---partie-1-:-calcul-propositionnel
        status_code
        200
        
        status_text
        OK
        format
        html
        content_type
        text/html; charset=UTF-8
        request_query
        []
        
        request_request
        []
        
        request_headers
        0 of 0
        array:24 [ "sec-ch-ua-mobile" => array:1 [ 0 => "?0" ] "sec-ch-ua" => array:1 [ 0 => ""HeadlessChrome";v="129", "Not=A?Brand";v="8", "Chromium";v="129"" ] "cache-control" => array:1 [ 0 => "no-cache" ] "pragma" => array:1 [ 0 => "no-cache" ] "cdn-loop" => array:1 [ 0 => "cloudflare; loops=1" ] "priority" => array:1 [ 0 => "u=0, i" ] "upgrade-insecure-requests" => array:1 [ 0 => "1" ] "user-agent" => array:1 [ 0 => "Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)" ] "cf-connecting-ip" => array:1 [ 0 => "3.139.103.88" ] "accept" => array:1 [ 0 => "text/html,application/xhtml+xml,application/xml;q=0.9,image/avif,image/webp,image/apng,*/*;q=0.8,application/signed-exchange;v=b3;q=0.7" ] "sec-fetch-site" => array:1 [ 0 => "none" ] "cf-visitor" => array:1 [ 0 => "{"scheme":"https"}" ] "sec-fetch-mode" => array:1 [ 0 => "navigate" ] "sec-fetch-user" => array:1 [ 0 => "?1" ] "x-forwarded-proto" => array:1 [ 0 => "https" ] "cf-ipcountry" => array:1 [ 0 => "US" ] "accept-encoding" => array:1 [ 0 => "gzip, br" ] "sec-fetch-dest" => array:1 [ 0 => "document" ] "sec-ch-ua-platform" => array:1 [ 0 => ""Windows"" ] "x-forwarded-for" => array:1 [ 0 => "3.139.103.88" ] "cf-ray" => array:1 [ 0 => "915fb54a8fca125d-ORD" ] "host" => array:1 [ 0 => "www.corspedia.com" ] "content-length" => array:1 [ 0 => "" ] "content-type" => array:1 [ 0 => "" ] ]
        request_server
        0 of 0
        array:50 [ "USER" => "www-data" "HOME" => "/var/www" "HTTP_SEC_CH_UA_MOBILE" => "?0" "HTTP_SEC_CH_UA" => ""HeadlessChrome";v="129", "Not=A?Brand";v="8", "Chromium";v="129"" "HTTP_CACHE_CONTROL" => "no-cache" "HTTP_PRAGMA" => "no-cache" "HTTP_CDN_LOOP" => "cloudflare; loops=1" "HTTP_PRIORITY" => "u=0, i" "HTTP_UPGRADE_INSECURE_REQUESTS" => "1" "HTTP_USER_AGENT" => "Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)" "HTTP_CF_CONNECTING_IP" => "3.139.103.88" "HTTP_ACCEPT" => "text/html,application/xhtml+xml,application/xml;q=0.9,image/avif,image/webp,image/apng,*/*;q=0.8,application/signed-exchange;v=b3;q=0.7" "HTTP_SEC_FETCH_SITE" => "none" "HTTP_CF_VISITOR" => "{"scheme":"https"}" "HTTP_SEC_FETCH_MODE" => "navigate" "HTTP_SEC_FETCH_USER" => "?1" "HTTP_X_FORWARDED_PROTO" => "https" "HTTP_CF_IPCOUNTRY" => "US" "HTTP_ACCEPT_ENCODING" => "gzip, br" "HTTP_SEC_FETCH_DEST" => "document" "HTTP_SEC_CH_UA_PLATFORM" => ""Windows"" "HTTP_X_FORWARDED_FOR" => "3.139.103.88" "HTTP_CF_RAY" => "915fb54a8fca125d-ORD" "HTTP_HOST" => "www.corspedia.com" "REDIRECT_STATUS" => "200" "SERVER_NAME" => "corspedia.com" "SERVER_PORT" => "443" "SERVER_ADDR" => "141.95.147.152" "REMOTE_USER" => "" "REMOTE_PORT" => "19758" "REMOTE_ADDR" => "172.69.59.194" "SERVER_SOFTWARE" => "nginx/1.18.0" "GATEWAY_INTERFACE" => "CGI/1.1" "HTTPS" => "on" "REQUEST_SCHEME" => "https" "SERVER_PROTOCOL" => "HTTP/2.0" "DOCUMENT_ROOT" => "/var/www/corspedia/public" "DOCUMENT_URI" => "/index.php" "REQUEST_URI" => "/ar/%D8%A7%D9%84%D8%AF%D9%88%D8%B1%D8%A7%D8%AA/introduction-%C3%A0-la-logique-informatique---partie-1-:-calcul-propositionnel" "SCRIPT_NAME" => "/index.php" "CONTENT_LENGTH" => "" "CONTENT_TYPE" => "" "REQUEST_METHOD" => "GET" "QUERY_STRING" => "" "SCRIPT_FILENAME" => "/var/www/corspedia/public/index.php" "PATH_INFO" => "" "FCGI_ROLE" => "RESPONDER" "PHP_SELF" => "/index.php" "REQUEST_TIME_FLOAT" => 1740234984.3398 "REQUEST_TIME" => 1740234984 ]
        request_cookies
        []
        
        response_headers
        0 of 0
        array:5 [ "content-type" => array:1 [ 0 => "text/html; charset=UTF-8" ] "cache-control" => array:1 [ 0 => "no-cache, private" ] "date" => array:1 [ 0 => "Sat, 22 Feb 2025 14:36:24 GMT" ] "set-cookie" => array:2 [ 0 => "XSRF-TOKEN=eyJpdiI6ImVQVEFVdElEZTM2dFZOVitEK1FCYXc9PSIsInZhbHVlIjoiSlBFVy80N3hEZjZRNTIrTE9icC80Tkt0c0pHM210dTQra2ZrYkExNS9YL2NTNThVVWQrdFFCUXY5VHdIV2JRRDV3ZittdWRyZGIwcFVPYm9Gai9ZbHBQU2xYSFdiRTZMcWNaSVZwTW1URVp5bHRaOElOdzFSMzZwMFo1b09sb2ciLCJtYWMiOiIwNDgwMjJhNjMwNWUzNGMwNDE0ZDY5ZDNmZDg4NGExMTA4ZTYxZjE4M2VkZjQ3MTFmYmY2NDUyNDQ5NzIyNWZkIiwidGFnIjoiIn0%3D; expires=Sat, 22 Feb 2025 16:36:24 GMT; Max-Age=7200; path=/; samesite=laxXSRF-TOKEN=eyJpdiI6ImVQVEFVdElEZTM2dFZOVitEK1FCYXc9PSIsInZhbHVlIjoiSlBFVy80N3hEZjZRNTIrTE9icC80Tkt0c0pHM210dTQra2ZrYkExNS9YL2NTNThVVWQrdFFCUXY5VHdIV2JRRDV3Zittd" 1 => "laravel_session=eyJpdiI6Im9ISG1kdDI4SFc4MmFaZnA5bFNZUGc9PSIsInZhbHVlIjoidE5XYmk3YjVrRUNkWjVpcm5MNDYzbmdwQUQydkMwZUdSaEorZGNIMGVkWFVCYkJEVjB4VkY0aFpRZHN5TDFBRWdkekxNUVZEQlNBZTl4ai95ZTl1TDBVUUhjbFFhZ2VJcmZBU3VHWDA4SFA2aVRVeUsxMHRScnAvU3FZdE9Mb2UiLCJtYWMiOiJmMWMyNTMyZGZhZGQ0NDkxZjYyYmJhZDMwYWY1M2RiYzEyNDBlODFkNTk5MjBiZmZhZTJjMzE2NDAwYmEwZDQ0IiwidGFnIjoiIn0%3D; expires=Sat, 22 Feb 2025 16:36:24 GMT; Max-Age=7200; path=/; httponly; samesite=laxlaravel_session=eyJpdiI6Im9ISG1kdDI4SFc4MmFaZnA5bFNZUGc9PSIsInZhbHVlIjoidE5XYmk3YjVrRUNkWjVpcm5MNDYzbmdwQUQydkMwZUdSaEorZGNIMGVkWFVCYkJEVjB4VkY0aFpRZHN5TDFBRWdk" ] "Set-Cookie" => array:2 [ 0 => "XSRF-TOKEN=eyJpdiI6ImVQVEFVdElEZTM2dFZOVitEK1FCYXc9PSIsInZhbHVlIjoiSlBFVy80N3hEZjZRNTIrTE9icC80Tkt0c0pHM210dTQra2ZrYkExNS9YL2NTNThVVWQrdFFCUXY5VHdIV2JRRDV3ZittdWRyZGIwcFVPYm9Gai9ZbHBQU2xYSFdiRTZMcWNaSVZwTW1URVp5bHRaOElOdzFSMzZwMFo1b09sb2ciLCJtYWMiOiIwNDgwMjJhNjMwNWUzNGMwNDE0ZDY5ZDNmZDg4NGExMTA4ZTYxZjE4M2VkZjQ3MTFmYmY2NDUyNDQ5NzIyNWZkIiwidGFnIjoiIn0%3D; expires=Sat, 22-Feb-2025 16:36:24 GMT; path=/XSRF-TOKEN=eyJpdiI6ImVQVEFVdElEZTM2dFZOVitEK1FCYXc9PSIsInZhbHVlIjoiSlBFVy80N3hEZjZRNTIrTE9icC80Tkt0c0pHM210dTQra2ZrYkExNS9YL2NTNThVVWQrdFFCUXY5VHdIV2JRRDV3Zittd" 1 => "laravel_session=eyJpdiI6Im9ISG1kdDI4SFc4MmFaZnA5bFNZUGc9PSIsInZhbHVlIjoidE5XYmk3YjVrRUNkWjVpcm5MNDYzbmdwQUQydkMwZUdSaEorZGNIMGVkWFVCYkJEVjB4VkY0aFpRZHN5TDFBRWdkekxNUVZEQlNBZTl4ai95ZTl1TDBVUUhjbFFhZ2VJcmZBU3VHWDA4SFA2aVRVeUsxMHRScnAvU3FZdE9Mb2UiLCJtYWMiOiJmMWMyNTMyZGZhZGQ0NDkxZjYyYmJhZDMwYWY1M2RiYzEyNDBlODFkNTk5MjBiZmZhZTJjMzE2NDAwYmEwZDQ0IiwidGFnIjoiIn0%3D; expires=Sat, 22-Feb-2025 16:36:24 GMT; path=/; httponlylaravel_session=eyJpdiI6Im9ISG1kdDI4SFc4MmFaZnA5bFNZUGc9PSIsInZhbHVlIjoidE5XYmk3YjVrRUNkWjVpcm5MNDYzbmdwQUQydkMwZUdSaEorZGNIMGVkWFVCYkJEVjB4VkY0aFpRZHN5TDFBRWdk" ] ]
        session_attributes
        0 of 0
        array:5 [ "_token" => "HTbc2UyW0Zh3RguMIrSiohKVAUOn1OL22q7vuCfb" "locale" => "ar" "_previous" => array:1 [ "url" => "https://www.corspedia.com/ar/%D8%A7%D9%84%D8%AF%D9%88%D8%B1%D8%A7%D8%AA/introduction-%C3%A0-la-logique-informatique---partie-1-:-calcul-propositionnel" ] "_flash" => array:2 [ "old" => [] "new" => [] ] "PHPDEBUGBAR_STACK_DATA" => [] ]